婼只OJ，，洛谷上都交过了在这里 $RE$ 。。。。。

洛谷上的题解多少有点抽象，都说这是 $DP$ 套 $DP$ 的板子题目。

下面将会详细介绍相关内容：

所谓 $dp$ 套 $dp$，就是一个外层 $dp$ 的状态是内层 $dp$ 数组构成的。当然因为我们很难存储一个 $dp$ 的数组，于是一般需要进行状态压缩。

对于这道题目来说，我们先考虑一个朴素的 $LCS$ 怎么做，显然有转移 $f_{i,j}=max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[S_i == T_i])$。

然后我们如何设计一个外层的 $dp$ 呢？我们考虑把上述 $dp$ 中的每一行 $f_i$ 压缩下来，扔到状态里面，然后另外一个状态我们可以直接枚举 $T$ 当前的长度。于是我们有外层$DP$ $F_{i,S}$。

现在我们考虑如何压缩这个状态。注意到 $f_{i,j}$ 最多比 $f_{i.j-1}$ 多一，于是我们可以压缩其对应的差分数组，显然状态数不超过 $2^{|S|}$ 。然后我们转移的时候只需要看当前这个内层 $DP$ 状态可能有哪些前置状态得到并且加贡献就可以了。然而具体实现的时候，为了方便实现，我们可以考虑刷表，这样写起来方便。

好的，思路基本上说完了。那么我们以上的思路都是知道它要 $dp$ 套 $dp$ 才想出来了以上的思路，那么我们为什么要这样来统计呢？我们返璞归真，如果写暴力的话显然可以直接枚举所有的 $S$ ，然后分别做 $LCS$ 进行统计，但是我们发现这其实是很亏的，因为我们发现有很多$S$对应的是同一个 $DP$ 序列，再有我们上面对 $LCS$ 转移本身的观察，发现它是很容易压缩的，于是就有了这样的思路。

CODE

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
char ch[20];
int num[20];
int ans[20];
int mp[200];
inline int lowbit(int x){return x&-x;}
inline int popcnt(int x){
 	if(!x)return 0;
	int ans=0;
	while(x)ans++,x-=lowbit(x);
	return ans;
}int f[1005][(1<<15)];
int nxt[4][(1<<15)];
int p[17],q[17],n;
inline int DP(int s0,int k){
	if(nxt[k][s0]!=-1)return nxt[k][s0];
	p[0]=q[0]=0;
	for(int i=1; i<=n; i++)p[i]=p[i-1]+((s0>>(i-1))&1);
	for(int i=1; i<=n; i++){
		q[i]=max(p[i],q[i-1]);
		q[i]=max(q[i],p[i-1]+(k==num[i]));
	}int s1=0;
	for(int i=1; i<=n; i++)s1|=((q[i]-q[i-1])<<(i-1));
	return nxt[k][s0]=s1;
}inline int add(int x,int y){
	x+=y;
	if(x>mod)x-=mod;
	return x;
}
int main(){
	mp['A']=0,mp['C']=1,mp['G']=2,mp['T']=3;
	int T;scanf("%d",&T);
	while(T--){
		scanf("%s",ch+1);
		n=strlen(ch+1);
		int m;scanf("%d",&m);
		for(int i=0; i<=3; i++)for(int j=0; j<(1<<n); j++)nxt[i][j]=-1;
		for(int i=1; i<=n; i++)num[i]=mp[(int)ch[i]];
		f[0][0]=1;
		for(int i=0; i<m; i++){
			for(int j=0; j<(1<<n); j++)f[i+1][j]=0;
			for(int k=0; k<=3; k++){
				for(int j=0; j<(1<<n); j++){
					int s=DP(j,k);
					if(s==-1)continue;
					f[i+1][s]=add(f[i+1][s],f[i][j]);
				}
			}
		}
		for(int i=0; i<=n; i++)ans[i]=0;
		for(int i=0; i<(1<<n); i++)ans[popcnt(i)]=add(ans[popcnt(i)],f[m][i]);
		for(int i=0; i<=n; i++)printf("%d\n",ans[i]%mod);
	}
	return 0;
} /*
1
GTC
3


*/

经验

经验*2