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; }