题意： 给出一个有n（<=2000）个数字的序列 a(ai <=2000) 再给出一个有m（m<=2000）个数字的序列 b （bi<=2000） ，定义波浪序列为：x1< x2 > x3 < x4（注意第一次必须是上升，不能是下降，也就是说第一项必须是波谷）。现在要求找到一个严格单调递增的序列 f：f1，f2，……fk。以及相对应的严格单调递增的序列g：g1，g2，……gk。（k>=1）使得每个a_fi = b_gi，同时满足a_f1,a_f2,a_f3……a_fk为波浪序列。求不同的fg映射有多少种选取方式。
a，b中分别从前向后选取k个数字。然后相对应的 a 中选择的每个位置的数字要和 b 中选择的对应位次的数字相同。（当然如果a数组出现过x，而b没有出现过x，显然x不可能被选取），而 f 、g 则是相对应的下标。要满足选取出来的这个数字序列是一个波浪序列。显然波浪序列中的数字分成两种：波峰和波谷。 总体来说，这个题就是a、b数组之间的匹配问题，同时满足是一个波浪序列
题解： 用波峰和波谷做为转移状态的手段，具体的看详解 里面写的很详细
代码：
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> using namespace std; #define clr(a, b) memset(a, b, sizeof(a)) #define pb(a) push_back(a) #define fir first #define se second #define LL long long #define ll long long typedef pair<int, int> pii; typedef pair<LL, int> pli; typedef pair<LL, LL> pll; const LL inf = 0x3f3f3f3f3f3f3f3f; const int maxn = 300100; double eps = 0.000001; double PI = acos(-1); LL mod = 998244353;; LL sum[2010][2],dp[2010][2]; int a[2010],b[2010],n,m; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); for(int i = 1;i <= m;i++) scanf("%d",&b[i]); clr(sum,0); clr(dp,0); LL ans = 0; for(int i = 1;i <= n;i++) { LL cnt1 = 1,cnt0 = 0; for(int j = 1;j <= m;j++) { dp[j][0] = dp[j][1] = 0; if(a[i] == b[j]) { dp[j][0] = cnt1; dp[j][1] = cnt0; ans = (ans + cnt1 + cnt0) % mod; } else if(b[j] < a[i]) cnt0 = (cnt0+sum[j][0])%mod; else cnt1 = (cnt1+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("%I64d\n",ans); } }