题目链接
题目翻译：
给出长度为n的序列a,
给出长度为m的序列b.
挑选一些下标f,
挑选一些下表g,
并且这两组下标都是升序排列的。
然后在选出Af == Bg，这些数，组成题目中所要求的波浪，求组成符合题目要求的波浪的序列数，最后答案模上一个数。
题目波浪的形式是：波谷，波峰，波谷，波峰。。。。。。所以波浪开头必须要是波谷。
动态规划题目，我的动态规律狠狠狠渣，现在还是个迷糊蛋。
设置dp[i][j][2].
dp[i][j][0] 以a[i],b[i]为结尾且作为波谷的方案数。
dp[i][j][1] 以a[i],b[i]为结尾且作为波峰的方案数。
由于每次可以固定序列a中的一个数，然后遍历整个b，序列，因此可以把三维的dp优化成二维，
dp[j][2]. 因为a[i]每次固定，则二维dp已经默认第一维就是a[i].
sum[j][0]代表以a[i],b[i]为结尾的且作为波谷的方案的总数。
sum[j][1]代表以a[i],b[i]为结尾的且作为波峰的方案的总数。
固定当前a[i]。与序列中的各个值比较。
如果a[i] == b[j] ,则，把a[i]作为波峰，波谷的方案数直接给dp[j][1]和dp[j][0],就可以了。这些方案数是由下面
的操作统计而来的。
如果a[i] > b[j]。因为固定a[i]的时候，我们是从a数组从前往后遍历的，那么a数组中的前i-1个数，已经
完成了与b数组中各个数字的比较，只要前数组a中前i-1个有与b[j]相等的数，假如这个数为a[k] {1<=k<i},
则一定已经存在以a[k],b[j]为结尾作为波峰和波谷的方案了，由于当前a[i]>b[j]，则a[i]对于b[j]来说，只能
做波峰，继续往后比较如果存在b[t]==a[i] (j<t<=m)，那么a[i]就可以加在b[j]作为波谷结尾的后面，做波峰，
则，a[i]做波峰的方案数,就应该在加上b[j]做为波谷的方案数。
同理a[i] < b[j]的时候，a[i]就可以做为波谷，则a[i]左为波谷的方案数，需要加上b[j]作为波峰结尾的方案数。
AC代码：
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; const int mod = 998244353; const int maxn = 2010; int sa[maxn]; ///序列a int sb[maxn]; ///序列b int dp[maxn][2]; ///dp[i][j][0]代表以a[i],b[j]为结尾，作为波谷的方案数，dp[i][j][1]代表以a[i],b[j]为结尾，作为波峰的方案数。 ///因为可以每次固定a[i],然后遍历b数组，这样的话，就自动默认第一维，可以把上面的数组变成二维的。 int sum[maxn][2]; ///sum[i][j][0]代表当前以a[i],b[j]结尾作为波谷的总方案数，sum[i][j][1]代表当前以a[i],b[j]结尾作为波峰的总方案数 int main() { int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&sa[i]); for(int i = 1; i <= m; i++) scanf("%d",&sb[i]); memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); long long ans = 0; for(int i = 1; i <= n; i++) { int waveBottom = 1,waveTop = 0; /**wavebottom为波谷，wavetop为波峰,由于题目说了波浪是从波谷开始的，所以只要单独 的一列序列是一定能做波谷的，所以波谷初始化1.**/ for(int j = 1; j <= m; j++) ///每次固定sa[i]，遍历sequence b。 { dp[j][0] = dp[j][1] = 0; if(sa[i]==sb[j]) ///两个序列的相同的数值，才能做波峰和波谷 { dp[j][0] = waveBottom; dp[j][1] = waveTop; ans = (ans + waveBottom + waveTop)%mod; } else if(sa[i]<sb[j]) { waveBottom = (waveBottom + sum[j][1])%mod; } else ///sa[i]>sb[j],sa[i]可以作为以sb[j]为波谷结尾的序列的波峰 { waveTop = (waveTop + sum[j][0])%mod; } } ///更新以a[i],b[j]作为波峰波谷结尾的总方案数 for(int j = 1; j <= m; j++) { if(sa[i] == sb[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; }
