题目链接：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;
}