题解 P4590 【[TJOI2018]游园会】
whyl
2020-04-28 17:10:08
***
[TJOI2018]游园会
***
题意：
给定 *N* ，*K* ，分别代表的是*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 表示当前结尾分别匹配到了 没有 ， *N* ，*NO* 的方案数
状态为 ： 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* 这一维滚动
统计答案 ：~~（ 这部分太简单。。）~~不想打字了 ， 直接放代码
***
代码：
```c++
#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;
}
```