题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6078
题意：求两个序列的公共波形子序列的个数。
解法：官方题解：
涨姿势，我只能说敝队现在真是被吊打，只能赛后补一补题。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 2010; int T,n,m; LL dp[maxn][2], s[maxn][2]; int a[maxn],b[maxn]; const int mod = 998244353; int main() { scanf("%d",&T); while(T--) { 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(dp,0,sizeof(dp)); memset(s,0,sizeof(s)); LL ans=0; LL cnt1,cnt2; for(int i=1; i<=n; i++) { cnt1=1,cnt2=0; //cnt1统计前面波谷的情况，同时自己属于波峰 //cnt0统计前面波峰的情况，同时自己属于波谷 for(int j=1; j<=m; j++) { if(a[i]==b[j])//相等更新对应波峰波谷的值 { dp[j][0]=cnt1;//波峰 dp[j][1]=cnt2;//波谷 ans=(ans+cnt1+cnt2)%mod;//答案 } else if(a[i]>b[j])//a[i]比b[j]大所以a可以在波峰 { (cnt2+=s[j][0])%=mod; } else { (cnt1+=s[j][1])%=mod;//相反 } } for(int j=1; j<=m; j++) { if(a[i]==b[j])//把上一轮a[i]的次数加上这一轮 { (s[j][0]+=dp[j][0])%=mod; (s[j][1]+=dp[j][1])%=mod; } } } printf("%lld\n", ans); } return 0; }
