题目链接：https://darkbzoj.cf/problem/3864
这个是DP套DP的典型例题。
常规LCS的求法：
设dp[i][j]表示到a[i],b[j]的LCS。
那么if \(a[i]!=b[j]\),then \(dp[i][j]=max(dp[i][j-1],dp[i-1][j])\)
if \(a[i]==b[j]\),then \(dp[i][j]=dp[i-1][j-1]+1\)
现在我们知道字符串a，但是不知道b。但是很显然的，对于b字符串，每增加一位（枚举），必然会有对相应LCS的贡献。
我们设f[i][s]表示当前处理到字符串b的第i位，且当前它与a的LCS的状态为s。g[s][0/1/2/3]表示在当前LCS状态为s的时候，在后面添加'A','T','C','G’之后的LCS情况。
那么可以列出递推式\(f[i][g[s][0/1/2/3]]+=f[i-1][s]\)
\(g\)数组的处理可以写到函数里，进行预处理。
然后就是要注意。。。。空间的问题，这题空间卡得太丧心病狂了。。。。。qwqwqwq
代码如下：
#include<cstring>
#include<cstdio>
#include<algorithm>
#define mod 1000000007
using namespace std;
int n,m,t;
int g[(1<<15)+2][4],f[1001][(1<<15)+2],ans[111],pre[16],now[16],a[16];
char ss[16];
inline int calc(int x)
{int cur_ans=0;for(int i=20;i>=0;i--)if(x&(1<<i))cur_ans++;return cur_ans;
}
inline int trans(char x)
{if(x=='A') return 0;else if(x=='T') return 1;else if(x=='C') return 2;else return 3;
}
inline int solve(int s,int k)
{memset(pre,0,sizeof(pre));memset(now,0,sizeof(now));for(int i=0;i<n;i++) pre[i+1]=pre[i]+((s>>i)&1);for(int i=1;i<=n;i++){if(k==a[i]) now[i]=max(now[i],pre[i-1]+1);now[i]=max(max(now[i],now[i-1]),pre[i]);}int cur_ans=0;for(int i=0;i<n;i++) cur_ans+=(now[i+1]-now[i])*(1<<i);return cur_ans;
}
int main()
{scanf("%d",&t);while(t--){memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(ans,0,sizeof(ans));scanf("%s",ss+1);n=strlen(ss+1);for(int i=1;i<=n;i++) a[i]=trans(ss[i])+1;int maxx=1<<n;scanf("%d",&m);for(int i=0;i<=maxx;i++)for(int j=1;j<=4;j++)g[i][j]=solve(i,j);f[0][0]=1;for(int i=1;i<=m;i++)for(int j=0;j<=maxx;j++)for(int k=1;k<=4;k++)f[i][g[j][k]]=(f[i][g[j][k]]+f[i-1][j])%mod;for(int i=0;i<=maxx;i++)ans[calc(i)]=(ans[calc(i)]+f[m][i])%mod;for(int i=0;i<=n;i++)printf("%d\n",ans[i]);}return 0;
}
转载于:https://www.cnblogs.com/fengxunling/p/10204604.html