AC. 梦想

frank_c1

[ZJOI 2013] 丽洁体

发布于2017年03月01日 | 暂无评论 | 390阅读 | 动态规划,字符串

题意简述

给定一个串s

现在你需要删去尽量少的字符,让其可以和模板串a*b*c匹配。

其中a,b,c是三个串,*可以匹配0个或多个字符。

1 \le |s|, |a|, |b|, |c| \le 50000,保证每个字符出现不超过500次。

算法讨论

难得的清真题。

考虑一个暴力。设f(i,j)为考虑到s的第i个字符,在模板串匹配到j位置的最小花费。则一般情况

f(i,j) = \min\{f(k,j-1) + i - k - 1 \; | \; k \lt j, s[i] = t[j]\}

特别注意在abbc之间的转移花费为0

我们现在考虑怎么运用题目条件来优化DP的过程。

考虑对于一个i的转移。我们一定是去更新f数组里面,s[i] == t[j]j位置,由于只有至多500个这样的j,我们有效的更新就只有500次。但还需要枚举k,这是不可接受的。

我们发现转移中和k有关的部分只有价值的计算。由于-k-1在下一次转移中一定会被计入贡献,所以不妨在k位置是就统计进去,于是价值的转移只和i有关了。

由于k只需要满足小于i,所以现在第一维的存在也毫无意义了,空间也优化到O(n),单次转移就是O(1)

时间复杂度O(nS),其中S是字符最多出现次数。