题解 P4590 【[TJOI2018]游园会】

2020-04-28 17:10:08



[TJOI2018]游园会


题意:

给定 NK ,分别代表的是A串和B串的长度 ,给定 B

字符集为 N O I 三个

并且 A 串 和 B 串 不会出现 连续的 NOI 作为字串

输出 K+1 行 ,i 行表示 A 串与 B 串 最长公共子序列长度为 i-1 的方案数

数据范围 N <=1000 K <= 15


题解:

据说这种方法叫做 DP 套 DP .....

定义状态 f[i] [S] [0/1/2] 表示 现在的长度为 i ,状态为 S ,

0,1,2 表示当前结尾分别匹配到了 没有 , NNO 的方案数

状态为 : B串的每个前缀 与 当前长度为 i的 A串 的 最长公共子序列长度 的差分数组

tips 差分是因为每次最多增加1,方便2进制状压)

定义状态 dp[i] [j] 表示 长度为 i ,和 B的前缀 匹配的最长公共子序列长度

转移: 枚举 下一位字符是 op ,将f 中的 S 前缀和 作为 dp 数组的初始化

在dp数组上 O(k) 更新 $$ dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+(s[i]==op)) $$ 在把 dp数组的值 变成 S
$$ f[i][S'][?]=f[i-1][S][?] $$ 由于空间原因 要把 i 这一维滚动

统计答案 :( 这部分太简单。。)不想打字了 , 直接放代码


代码:

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define re register

const int mod=1e9+7;

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar();
    return x*f;
}

int f[2][40005][3],dp[2][25],n,m,cnt[40005],ans[25];
char s[25];

inline void upd(int j){
    for(re int i=1;i<=m;i++) dp[0][i]=dp[0][i-1]+(j&1),j>>=1;
}

inline int enc(){
    int res=0;
    for(re int i=1;i<=m;i++) if(dp[1][i]-dp[1][i-1]) res|=(1<<(i-1));
    return res;
}

inline void trans(int i,int j,char opt,int w,int dat){
    upd(j);
    for(re int p=1;p<=m;p++) dp[1][p]=max(dp[0][p],max(dp[1][p-1],dp[0][p-1]+(opt==s[p]))); 
    f[i][enc()][w]=(f[i][enc()][w]+dat)%mod;
}

signed main(){
    n=read();m=read();
    for(int i=1;i<=m;i++) cin>>s[i];
    f[0][0][0]=1;int full=(1<<m);
    for(int i=0;i<n;i++){
        int now=i&1,nxt=now^1;
        memset(f[nxt],0,sizeof(f[nxt]));
        for(int j=0;j<full;j++){
            if(f[now][j][0]){
                trans(nxt,j,'N',1,f[now][j][0]);
                trans(nxt,j,'O',0,f[now][j][0]);
                trans(nxt,j,'I',0,f[now][j][0]);
            }
            if(f[now][j][1]){
                trans(nxt,j,'N',1,f[now][j][1]);
                trans(nxt,j,'O',2,f[now][j][1]);
                trans(nxt,j,'I',0,f[now][j][1]);
            }
            if(f[now][j][2]){
                trans(nxt,j,'N',1,f[now][j][2]);
                trans(nxt,j,'O',0,f[now][j][2]);
            }
        }
    }
    for(int i=1;i<full;i++) cnt[i]=cnt[i>>1]+(i&1);
    for(int i=0;i<full;i++) for(int j=0;j<=2;j++) ans[cnt[i]]=(ans[cnt[i]]+f[n&1][i][j])%mod;
    for(int i=0;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}