http://www.lydsy.com/JudgeOnline/problem.php?id=3864

?

題意：

給你一個DNA序列，求有多少個長度為m的DNA序列和給定序列的LCS為0，1，2....

?

求LCS方式：f[i][j]=max（f[i-1][j],f[i][j-1],f[i-1][j-1]*(s[i]==t[j])）

固定了i，相鄰的j的f[i][j]值最多相差1

dp[i][j] 表示長度為i的DNA序列，將“f[ |S| ][j+1]是否比f[ |S| ][j] 大1” 這個狀態壓縮為j的方案數

若我們知道?狀態j加上一個字母k可以到狀態nxt[j][k]

那么dp[i+1][nxt[j][k]]+=dp[i][j]

?

關鍵是如何求得nxt[j][k]

再一次DP

枚舉所有的狀態i

令f[j] 表示加上字母k之前的LCS長度，g[j]表示加上字母k之后的LCS長度

g[j]=max(g[j-1],f[j])

如果加上的字母k和原序列第j個字母匹配 g[i]=max(g[j],f[j-1]+1)

g求完后，項鄰的兩個g要么相等，要么相差1

再把這個狀態壓縮起來即可

?

#include<cstdio> #include<cstring> #include<algorithm>using namespace std;const int mod=1e9+7;int m;char ss[16]; int L,S; int s[16];int ch[26];int f[16],g[16]; int nxt[1<<15][4];int dp[2][1<<15]; int ans[16];void pre() {int len; int c[16];for(int i=0;i<S;++i){memset(f,0,sizeof(f));for(int j=1;j<=L;++j) f[j]=f[j-1]+(i>>j-1&1);for(int k=0;k<4;++k){for(int j=1;j<=L;++j){g[j]=max(g[j-1],f[j]);if(s[j]==k) g[j]=max(g[j],f[j-1]+1);}nxt[i][k]=0;for(int j=0;j<L;++j)if(g[j+1]-g[j]) nxt[i][k]+=1<<j;}} }int count(int x) {int sum=0;while(x){sum+=x&1;x>>=1;}return sum; }void DP() {memset(dp,0,sizeof(dp));int now=1,last=0;dp[0][0]=1;for(int i=1;i<=m;++i){memset(dp[now],0,sizeof(dp[now]));for(int j=0;j<S;++j)for(int k=0;k<4;++k){dp[now][nxt[j][k]]+=dp[last][j];dp[now][nxt[j][k]]-=dp[now][nxt[j][k]]>=mod ? mod : 0;}swap(now,last);}memset(ans,0,sizeof(ans));int t;for(int i=0;i<S;++i) {t=count(i);ans[t]+=dp[last][i];ans[t]-=ans[t]>=mod ? mod : 0;}for(int i=0;i<=L;++i) printf("%d\n",ans[i]); }int main() {ch['A'-'A']=0;ch['C'-'A']=1;ch['G'-'A']=2;ch['T'-'A']=3;int T;scanf("%d",&T);while(T--){scanf("%s",ss+1);scanf("%d",&m);L=strlen(ss+1);S=1<<L;for(int i=1;i<=L;++i) s[i]=ch[ss[i]-'A'];pre();DP();}return 0; }

?

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/8454799.html

總結

以上是生活随笔為你收集整理的bzoj千题计划241：bzoj3864: Hero meet devil的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。