题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6078
题意：求两个序列的公共波形子序列的个数。
解法：
类似于最长公共上升子序列，对于每个i，只考虑存在j使得a[i]==b[j]的情况。
dp[i][j][0]表示以a[i]和b[j]为公共序列结尾且为波谷的情况总和。
dp[i][j][1]则表示波峰的情况总和。
S[i][j][0]表示sum(dp[k][j][0] | 1<=k<=j-1)。
S[i][j][1]则表示sum(dp[k][j][1] | 1<=k<=j-1)。
那么对于每个a[i]，只有存在j使得b[j]==a[i]时，dp[i][j][0]等于sum(S[i-1][k][1] |
1<=k<=j-1&&b[k]>a[i])+1，dp[i][j][1]等于sum(S[i-1][k][0] |
1<=k<=j-1&&b[k]<=a[i]-1)
当然还可以滚动数组优化这个DP，甚至直接省掉第一维。
#include<bits/stdc++.h> using namespace std; const int maxn = 2005; const int mod = 998244353; int sum[maxn][maxn][2]; int dp[maxn][maxn][2]; int a[maxn], b[maxn]; int main() { int T; scanf("%d", &T); while(T--) { int n, m; scanf("%d %d", &n, &m); memset(dp, 0, sizeof(dp)); memset(sum, 0, sizeof(sum)); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= m; i++) scanf("%d", &b[i]); int ans = 0; for(int i = 1; i <= n; i++) { int cnt0 = 0, cnt1 = 1; for(int j = 1; j <= m; j++) { if(a[i] == b[j]) { dp[i][j][0] = cnt1; dp[i][j][1] = cnt0; (ans += (cnt1 + cnt0) % mod) %= mod; } else if(a[i] > b[j]) (cnt0 += sum[i - 1][j][0]) %= mod; else (cnt1 += sum[i - 1][j][1]) %= mod; } for(int j = 1; j <= m; j++) { sum[i][j][0] = sum[i - 1][j][0]; sum[i][j][1] = sum[i - 1][j][1]; if(a[i] == b[j]) { (sum[i][j][0] += dp[i][j][0]) %= mod; (sum[i][j][1] += dp[i][j][1]) %= mod; } } } printf("%d ", ans); } return 0; }