hud 6078 Wavel Sequence
題目大意：給你兩個序列a，b，讓你找出兩個函數 f 和 g 使得 a[f]=b[g]，并且a[f1]，a[f2]，a[f3]……a[fk]滿足 序列a1 < a2 > a3 < a4……為你滿足關系的 f 和 g有多少種
解題思路：不難想到我們可以單獨考慮每個數字，看它作為波峰有多少種情況，波谷有多少種情況，然后求和。但是具體怎么求每個數字作為波峰的情況和波谷的情況呢？因為我們要用a數組來構造波浪，所以我們不妨可以將a數組固定，然后根據條件在b數組中尋找a中每個數據可能作為波峰和波谷的所有情況。具體要怎么做看代碼

#include <bits/stdc++.h>using namespace std; const int mod = 998244353; int dp[2005][2],sum[2005][2]; /** dp[][0]用來保存b數組中這個值作為波谷的情況 dp[][1]用來保存b數組中這個值作為波峰的情況 sum[][0]用來保存b數組中這個值作為波谷的總情況 sum[][1]用來保存b數組中這個值作為波峰的總情況 */ int main() {int T;scanf("%d",&T);while(T--){memset(dp,0,sizeof(dp));memset(sum,0,sizeof(sum));int n,m,a[2005],b[2005];scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int j = 1; j <= m;j++)scanf("%d",&b[j]);long long ans = 0,cnt0,cnt1;///ans用來存f和g共有多少種選擇，從cnt1用來保存當前值做波峰的情況，cnt0用來保存做波谷的情況for(int i=1;i<=n;i++){cnt0 = 1;cnt1 = 0;///因為每個數字都可以單獨作為波谷，所以波谷初始值為1.for(int j = 1; j <= m; j ++){dp[j][0] = dp[j][1] = 0;if(a[i] == b[j])///表示此時已經找到一組可以為波浪的數據，并將這個波峰，波谷的值記下，方便后邊使用，ans要累加上{dp[j][0] = cnt0;dp[j][1] = cnt1;ans = (ans + cnt0 + cnt1)%mod;}else if(a[i] > b[j])///如果當前這個值比a[i]要小的話說明a[i]可以作為波峰，這個時候它可以承接前邊所有的波谷的情況，所以要加上前邊波谷的所有情況cnt1 = (cnt1 + sum[j][0])%mod;else///如果當前這個值比a[i]要大的話說明a[i]可以作為波谷，這個時候它可以承接前邊所有的波峰的情況，所以要加上前邊波谷的所有情況cnt0 = (cnt0 + sum[j][1])%mod;}for(int j=1;j<=m;j++){///每次都要記錄下每個點作為波峰和波谷的總情況if(a[i] == b[j]){sum[j][0] = (sum[j][0]+dp[j][0])%mod;sum[j][1] = (sum[j][1]+dp[j][1])%mod;}}}printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hud 6078 Wavel Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。