LGP4590题解

这题好像比较牛逼，好像又不是怎么样。

考虑两个串是如何计算 LCS 的。

这还不简单？\(dp[n][m]=\max(\max(dp[n-1][m],dp[n][m-1]),[s[n]==t[m]]dp[n-1][m-1])\)。

我们发现一件事情：\(dp[n][m]-dp[n][m-1]\leq 1\)。

接下来引入一个叫 DP 套 DP 的神秘玩意儿。

大概其实就是在 DP 的转移 DAG（或者 DFA）上面搞事情。

我们对 \(t\) 状压，表示当前的 \(s\) 和 \(t\) 的匹配状态。

我们如果知道匹配状态是可以直接还原 dp 数组的。我们直接还原，然后枚举 \(s\) 当前是哪一个字符，然后把转移边丢出来就好了。

以及，这个转移 DAG 包含了所有可能的边。

所有我们需要做的就是枚举当前匹配状态和下一个字符，然后把转移边丢出来。

然后转移就好了。

对于 NOI，只需要额外记录当前匹配到哪个字符，再处理一下即可。

复杂度 \(O(m2^k+k2^k)\)。

#include<cstdio>

typedef unsigned ui;

const ui mod=1e9+7;

ui n,m,lim,t[20],ans[20],ppc[1<<15],trans[1<<15|1][3],f[1<<15|1][3],g[1<<15|1][3];char s[20];

ui dp[2][20];

inline ui max(const ui&a,const ui&b){

	return a>b?a:b;

}

inline void Add(ui&a,const ui&b){

	if((a+=b)>=mod)a-=mod;

}

inline void init(){

	lim=1<<m;

	for(ui i=0;i<m;++i)t[i]=s[i]=='N'?0:s[i]=='O'?1:2;

	for(ui S=0;S<lim;++S){

		for(ui i=0;i<m;++i)dp[0][i]=S>>i&1;

		for(ui i=1;i<m;++i)dp[0][i]+=dp[0][i-1];

		for(ui s=0;s<3;++s){

			dp[1][0]=dp[0][0];

			if(s==t[0])dp[1][0]=1;

			for(ui i=1;i<m;++i){

				dp[1][i]=max(dp[1][i-1],dp[0][i]);

				if(s==t[i])dp[1][i]=max(dp[1][i],dp[0][i-1]+1);

			}

			for(ui i=1;i<m;++i)trans[S][s]|=dp[1][i]-dp[1][i-1]<<i;trans[S][s]|=dp[1][0];

		}

	}

}

signed main(){

	scanf("%u%u%s",&n,&m,s);init();f[0][0]=1;

	for(ui i=0;i<n;++i){

		for(ui S=0;S<lim;++S){

			if(f[S][0]){

				Add(g[trans[S][0]][1],f[S][0]);

				Add(g[trans[S][1]][0],f[S][0]);

				Add(g[trans[S][2]][0],f[S][0]);

			}

			if(f[S][1]){

				Add(g[trans[S][0]][1],f[S][1]);

				Add(g[trans[S][1]][2],f[S][1]);

				Add(g[trans[S][2]][0],f[S][1]);

			}

			if(f[S][2]){

				Add(g[trans[S][0]][1],f[S][2]);

				Add(g[trans[S][1]][0],f[S][2]);

			}

		}

		for(ui S=0;S<lim;++S){

			f[S][0]=g[S][0];f[S][1]=g[S][1];f[S][2]=g[S][2];

			g[S][0]=g[S][1]=g[S][2]=0;

		}

	}

	for(ui S=0;S<lim;++S){

		ppc[S]=ppc[S>>1]+(S&1);

		for(ui i=0;i<3;++i)Add(ans[ppc[S]],f[S][i]);

	}

	for(ui i=0;i<=m;++i)printf("%u\n",ans[i]);

}

巴特西

LGP4590题解

最新文章

热门文章