BZOJ 2121 字符串游戏

发表于 | 更新于

Link

我只想说：是谁想出的这么＊＊的DP？！

Solution

  1. 决定一个区间能否被删去的是其能否在一系列变化之后被一个串完全匹配掉。
  2. 不管原串如何变化，一堆小串是不动的

由此可以得到一个思路：区间能否被删除取决于小串；而小串是固定的，可以表示出区间变化之后的形态。也就是说，小串可以表示出可以决定删除的DP状态。 那就从小串入手，设计状态f[l][r][i][d]f[l][r][i][d]表示区间[l,r][l,r]删到最后能否只剩下第ii个小串的前dd个字符。可以看出，任何一个合法的删除序列，对于区间嵌套起来的一组消除，一定可以用这个状态表示。转移的时候需要一个辅助状态c[l][r]c[l][r]，表示区间[l,r][l,r]能否被完全消除，然后就做就行了。

Tips

设计DP状态的时候要找决定答案的量，要找不变或者确定可知的量。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "lucida"
const int MAXL=160,MAXS=35,MAXP=25;
int main() {
	freopen("input","r",stdin);
	static bool f[MAXL][MAXL][MAXS][MAXP],c[MAXL][MAXL];
	static char L[MAXL],S[MAXS][MAXP];
	static int len[MAXS],minv[MAXL];
	int sn;
	is>>(L+1)>>sn;
	int n=strlen(L+1);
	for(int i=1;i<=sn;++i) {
		is>>(S[i]+1);
		len[i]=strlen(S[i]+1);
	}	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=sn;++j)
			f[i][i-1][j][0]=1;
	//f[l][r][i][d] 区间[l,r]能否匹配到S[i]的前t位
	//c[l][r] 区间[l,r]能否删干净
	for(int range=1;range<=n;++range)
		for(int l=1,r=range;r<=n;++l,++r) 
			for(int i=1;i<=sn;++i) {
				for(int d=1;d<=len[i];++d) {
					f[l][r][i][d]=(f[l][r-1][i][d-1] && L[r]==S[i][d]);
					for(int p=l;p<=r-1;++p)
						f[l][r][i][d]|=(f[l][p][i][d] && c[p+1][r]);
				}
				c[l][r]|=f[l][r][i][len[i]];
			}
	for(int i=1;i<=n;++i) {
		minv[i]=minv[i-1]+1;
		for(int j=1;j<=i;++j)
			if(c[j][i])
				chkmn(minv[i],minv[j-1]);
	}
	os<<minv[n]<<'\n';
	return 0;
}