CF1366G - Construct the String

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缺陷就在于:

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

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

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

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

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

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]);
}
上一篇:锁的封装


下一篇:Scala 面向对象(二)construct+抽象类+接口trait