2017多校第4场 HDU 6078 Wavel Sequence DP,计数

HDU 6078 Wavel Sequence DP,计数"/>

2017多校第4场 HDU 6078 Wavel Sequence DP,计数

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