luogu P4590 [TJOI2018]游园会 dp套dp

LINK：游园会

容易想到设\(f[i][j][k][l]\)前i个字符 j表示状压的w个字符状态为j 长度<=k 匹配到了NOI的第l个位置的方案数.

不过只能得到30分。

考虑优化其实优化就只能优化如何快速得到LCS 这个问题 \(3^15\cdot 15\)的状态量无法很难接受。

考虑降低这个状态量。考虑如果在一个自动机上那么我们这个状态就可以表示匹配到了自动机上某个节点。

不过最长公共子序列自动机并不存在。

考虑人为构造这个东西考虑求两个串的最长公共子序列的dp.

\(dp_{i,j}\)表示A串前i个字符B串前j个字符的最大长度.

容易得到转移:\(dp_{i,j}=max(dp_{i-1,j},dp{i,j-1},dp_{i-1,j-1}+[A_i==B_j])\)

那么其实只要知道\(dp_i-1\)这个数组和当前这个字符\(A_i\)就可以推向下一个字符。

进一步的以\(dp_i\)为最长公共子序列的节点那么每次转移只需要枚举下一个字符是谁就可以很容易的重新得到新的LCS的状态和长度.

这样就可以把上述的那么大的状态量压缩成了这样的dp数组不过直接存一个数组是需要hash的。

可以观察得到 \(dp_i\)是不降的可以将其差分就得到了一个二进制串最终状态量为\(2^w\) 可以通过此题.

const int MAXN=1010,maxn=35010;

int n,k,u,maxx;

int f[2][maxn][3];

char a[MAXN];

int g[2][MAXN],sum[maxn],ans[MAXN];

inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}

inline void jy(int s)

{

	rep(1,k,i)g[0][i]=s>>i-1&1;

	rep(1,k,i)g[0][i]+=g[0][i-1];

}

inline int ys()

{

	int S=0;

	rep(1,k,i)if(g[1][i]-g[1][i-1])S|=1<<(i-1);

	return S;

}

inline void update(int s,int l,char c,int w)

{

	jy(s);

	rep(1,k,i)

	{

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

		if(c==a[i])g[1][i]=max(g[1][i],g[0][i-1]+1);

	}

	int j=ys();add(f[u][j][l],w);

}

int main()

{

	freopen("1.in","r",stdin);

	gt(n);gt(k);gc(a);

	maxx=1<<k;--maxx;

	f[u][0][0]=1;

	rep(1,n,i)

	{

		u=u^1;

		rep(0,maxx,j)rep(0,2,k)f[u][j][k]=0;

		rep(0,maxx,j)

		{

			if(f[u^1][j][0])

			{

				update(j,1,'N',f[u^1][j][0]);

				update(j,0,'O',f[u^1][j][0]);

				update(j,0,'I',f[u^1][j][0]);

			}

			if(f[u^1][j][1])

			{

				update(j,1,'N',f[u^1][j][1]);

				update(j,2,'O',f[u^1][j][1]);

				update(j,0,'I',f[u^1][j][1]);

			}

			if(f[u^1][j][2])

			{

				update(j,1,'N',f[u^1][j][2]);

				update(j,0,'O',f[u^1][j][2]);

			}

		}

	}

	rep(0,maxx,i)

	{

		sum[i]=sum[i>>1]+(i&1);

		rep(0,2,j)add(ans[sum[i]],f[u][i][j]);

	}

	rep(0,k,i)put(ans[i]);

	return 0;

}

巴特西

luogu P4590 [TJOI2018]游园会 dp套dp

最新文章

热门文章