[DP套DP] BZOJ3864: Hero meet devil

题意

给出一个长度为n的基因序列S(仅包含字母ACGT的串)和一个数m。
对于每个x=0~n，求有多少个长度为m的基因序列T满足LCS(S,T)=x。
n,m<=15

题解

外层:$f(i,g)$ 表示T考虑到前i位，状态为s的方案数。
这个内层的状态g是一个长度为n的序列，表示LCS(i,1~n)这个的第二维。
可以想到这个序列是不降的且每次最多加1，所以只需要差分后用一个二进制数保存即可。
内层状态的转移需要预处理出来，$nxt[g][k]=g_{now}$表示在g这个状态时，在T后多加一个字母k得到的新状态$g_{now}$。具体转移的话就是和经典的二维DP求LCS一样的道理。
然后外层每次枚举T后面放那个字母，然后简单转移即可。

#include
#include
#include
using namespace std;
const char ltr[4]={'A','C','G','T'};
const int MOD=1000000007;
int _test,n,m,nxt[(1<<15)+5][4],f[2][(1<<15)+5],ans[20],res[(1<<15)+5];
int g1[20],g2[20];
char st[20];
void Pre(){for(int s=0;s<=(1<1;s++){g1[0]=0; for(int i=1;i<=n;i++) g1[i]=g1[i-1]+((s>>i-1)&1); res[s]=g1[n];for(int k=0;k<=3;k++){g2[0]=0;for(int i=1;i<=n;i++){g2[i]=max(g2[i-1],g1[i]);if(ltr[k]==st[i]) g2[i]=max(g2[i],g1[i-1]+1);  }nxt[s][k]=0; for(int i=1;i<=n;i++) nxt[s][k]|=((g2[i]-g2[i-1])<1);}}
}
int main(){freopen("bzoj3864.in","r",stdin);freopen("bzoj3864.out","w",stdout);scanf("%d",&_test);while(_test--){scanf("%s%d",st+1,&m); n=strlen(st+1);Pre();memset(f,0,sizeof(f)); f[0][0]=1;for(int i=0;i<=m-1;i++){memset(f[(i&1)^1],0,sizeof f[(i&1)^1]);for(int s=0;s<=(1<1;s++) for(int k=0;k<=3;k++) f[(i&1)^1][nxt[s][k]]=(f[(i&1)^1][nxt[s][k]]+f[i&1][s])%MOD;}memset(ans,0,sizeof ans);for(int s=0;s<=(1<1;s++) ans[res[s]]=(ans[res[s]]+f[m&1][s])%MOD;for(int i=0;i<=n;i++) printf("%d\n",ans[i]); }   return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！