HDU-4899 第一次写dp套dp
观察普通LCS方程 f[i][j]=max(f[i][j-1],f[i-1][j],f[i-1][f-1]+1) 转移过程可以当作给串增加1个字符后，f[i-1]到 f[i] 的变化 于是我们只要处理好dp数组的状态加一个字符到另一个状态的转移,从长度为0的串一直加到m， 便可以知道长度为m时的dp数组的状态。对最后每个dp数组状态计算它的贡献即可。 怎么保存dp数组状态呢？ 因为LCS与后一项比最多增加1。只要记录增量就好～ 即把每一项相对前一项的增量压缩为状态。
#include<bits/stdc++.h> using namespace std; const int MAXN=(1<<15)+7; const int MOD=1e9+7; const char w[]={"AGCT"}; char s[30]; int ans[30]; int tr[MAXN][4],tot; int cnt[MAXN],g[2][MAXN],m; int f1[20],f2[20]; void init() { for(int i=0;i<1<<tot;i++) { for(int j=1;j<=tot;j++)//f[x-1]数组 f1[j]=f1[j-1]+(i>>(j-1)&1); cnt[i]=f1[tot]; for(int j=0;j<4;j++)//枚举第x个字符 { for(int k=1;k<=tot;k++)//更新dp数组 { //f[i][j]=max(f[i][j-1],f[i-1][j],f[i-1][f-1]+1); f2[k]=max(f2[k-1],f1[k]);//f[x]数组 if(s[k]==w[j]) f2[k]=f1[k-1]+1; } tr[i][j]=0; for(int k=1;k<=tot;k++) if(f2[k]-f2[k-1]) tr[i][j]|=1<<(k-1); // printf("%d %d %d %d\n",i,j,tr[i][j],f1[tot]); } } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%s%d",s+1,&m); tot=strlen(s+1); init(); memset(ans,0,sizeof(ans)); for(int j=0;j<1<<tot;j++) g[0][j]=0; g[0][0]=1; for(int i=1;i<=m;i++) for(int j=0;j<1<<tot;j++) { if(g[~i&1][j]) for(int k=0;k<4;k++) (g[i&1][tr[j][k]]+=g[~i&1][j])%=MOD; g[~i&1][j]=0; } for(int i=0;i<1<<tot;i++) { (ans[cnt[i]]+=g[m&1][i])%=MOD; } for(int i=0;i<=tot;i++) printf("%d\n",ans[i]); } }