hdu6078

发表于 | 分类于

dp


题意

一个序列a1,a2,a3…被称为“wavel”，当且仅当a1a3a2<a6…
给定序列a1,a2,a3…an和序列b1,b2,b3…bm，有多少序列是“wavel”且为a和b的子序列.

  • 1<=n,m<=2000

题解

  • dp[i][j][k]表示a序列的第i个数和b序列的第j个数为当前序列的最后一个数，且为波峰/波谷的方案数，k为0表示波谷，k为1表示波峰。
  • 继续优化，s[i][j][k]表示序列的最后一个数为b[j]，在a序列中最后一个数下标为1~i-1的dp[i][j][k]的和。
  • 那么在固定i，从小到大枚举j的过程中，由a[i]即可知道当前b[j]应该取什么值，然后就能得到答案。
  • 复杂度O(n^2)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define maxn 2010
int s0[maxn],s1[maxn];
int dp[maxn][2];
int a[maxn],b[maxn];
int main(){
    int ca;
    scanf("%d",&ca);
    while(ca--){
        memset(s0,0,sizeof(s0));
        memset(s1,0,sizeof(s1));
        int n,m,ans=0;
        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]);
        for(int i=1;i<=n;i++){
            int c0=0,c1=0;
            for(int j=1;j<=m;j++){
                if(a[i]==b[j]){
                    dp[j][0]=(c1+1)%mod;
                    dp[j][1]=c0;
                    ans=(ans+dp[j][0])%mod;
                    ans=(ans+dp[j][1])%mod;
//                    printf("%d %d : %d %d\n",i,j,dp[j][0],dp[j][1]);
                }
                else dp[j][0]=dp[j][1]=0;
                if(a[i]>b[j]) c0=(c0+s0[j])%mod;
                else if(a[i]<b[j]) c1=(c1+s1[j])%mod;
            }
            for(int j=1;j<=m;j++){
                s0[j]=(s0[j]+dp[j][0])%mod;
                s1[j]=(s1[j]+dp[j][1])%mod;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
1
3 5
1 5 3
4 1 1 5 3
*/