CF1366G - Construct the String

题目大意

给定一个初始串$S$和目标串$T$

其中$S$除了包含字母外还包含删除标记’.’

具体的$S$表示的字符串$f(S)$，就是依次加入每个字母，或者在删除标记处删除上一个字符（不存在这个字符则非法）

求删除$S$中最少的字符，使得$f(S’)=T$


吐槽

$O(n^2)$出$n\leq 10^4$???



朴素dp分析

这种题目容易想到记录在$T$中匹配位置的$dp$，通过枚举$S$的每一个字符

1.匹配

2.手动删除

3.被’.’删除

然而被’.’删除的情况实际难以处理，因为无法额外记录待定的’.’个数


基于括号树的思路

考虑对于不完全的括号序列的包含关系建立树，注意到

1.一个已经和’.’匹配的字符，不需要考虑它被手动删除的情况

2.一个字符能够保留，当且仅当所有跨过其的右括号被删除

跨过其的右括号即祖先中的右括号

所以此时dp决策可以简单地归纳为

1.保留一整个匹配括号的子树，进入后面的匹配

2.否则，删除右括号，并且决定自己这个字符是否匹配，然后递归进入子树

代码没写


更简洁的表述

实际上与上面类似，但是更加简化了模型，转移可以简单归纳为

1.匹配当前字符

2.删除当前字符

3.找到当前字符匹配右括号，跳过这一段

原理：

实际上朴素dp缺陷就在于：

如果当前这个字符被后面的某一个’.’删除，却又无法匹配时，无法被加入状态

此时手动补充直接跳到删除这个字符的位置

充分性理解：在新串中匹配该字符的右括号 和 当前后缀中匹配该字符的括号相同

如果要让这个字符被’.’删除，那么到当前后缀中匹配该字符的括号为止，中间的部分不可能保留

手动删除只会让匹配该字符的括号右移，这不会更优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N=10010,P=1e9+7;

int n,m;
char s[N],t[N];
int dp[N][N];

int main(){
	scanf("%s%s",s,t),n=strlen(s),m=strlen(t);
	rep(i,0,n) memset(dp[i],63,(min(m,i)+2)<<2);
	rep(i,*dp[0]=0,n-1) {
		if(s[i]!='.') {
			int j=i,c=0;
			do c+=s[j++]=='.'?-1:1;
			while(c && j<n);
			if(!c) rep(k,0,min(m,i)) cmin(dp[j][k],dp[i][k]);
		}
		rep(j,0,min(m,i)) {
			cmin(dp[i+1][j],dp[i][j]+1);
			if(s[i]==t[j]) cmin(dp[i+1][j+1],dp[i][j]);
		}
	}
	printf("%d\n",dp[n][m]);
}