题意：
想在有两个序列a，b。从两个序列中挑出相同数量的数字，按照原本的顺序，有两 个要求。 1. 两个序列相同 2. 序列成波浪，就是第一个数字小，第二个数字大，依次类推，但是第一个数字 一定是最小的 最后问满足这样条件的挑选一共有多少种。
思路：
枚举每一个a[i], 算出每一个a[i]为挑出序列末尾的数字的贡献次数，每一个a[i],肯定都 要遍历整个b序列，当然数据量只有2000，所以算法复杂度为O（n^2） 也是没有问 题的。 定义： dp[j][0] 为以b序列第j结尾为谷底的波浪满足的次数。 dp[j][1] 为以b序列第j结尾为谷峰的波浪满足的次数。 sum[j][0] 为以b序列第j结尾为谷底的波浪满足的“总”次数。 sum[j][1] 为以b序列第j结尾为谷峰的波浪满足的“总”次数。 上面的定义不是很容易理解。 因为每一次枚举a[i] 的时候都是重新计算了一次dp[j][0] 和 dp[j][1] ,所以sum[j][0] 计 算的是每次计算的总和。 我们思考每次dp[j][0] 和dp[j][1] 的贡献值，我们知道只有当 a[i]==a[j] 的时候才 会有贡献值，对于dp[j][0] 来说，当 a[i]==a[j] 的时候，它是为谷底的情况，那 么只需要把之前已经算出的a[i] < b[k] （k < i）已经存在的情况在加上a[i] 就是一 个新的满足条件的序列。 dp[j][1] 同理。每次dp之后要记录sum[j] 的值。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 2005; const int mod = 998244353; int n,m,a[maxn],b[maxn]; long long sum[maxn][2],dp[maxn][2]; int main() { //freopen("in.txt","r",stdin); int tt; scanf("%d",&tt); while(tt--) { 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]); } memset(sum,0,sizeof(sum)); long long ans = 0; for(int i = 1;i <= n; i++) { int cnt0 = 1,cnt1 = 0; for(int j = 1;j <= m; j++) { dp[j][1] = dp[j][0] = 0; if(a[i] == b[j]) { dp[j][0] = (dp[j][0] + cnt0)%mod; dp[j][1] = (dp[j][1] + cnt1)%mod; ans = (ans + cnt0 + cnt1)%mod; } else if(a[i] > b[j]) cnt1 = (cnt1 + sum[j][0])%mod; else 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("%I64d\n",ans); } return 0; }