CF1858D

· · 题解

本题解作者是一个赛时没看题面，赛后一眼秒掉的小丑。

Sol

我们先扔掉那些乱七八糟的情况，只考虑长度最长的那个连续 0 子串。

我们需要枚举所有可能的最长连续 0 子串。

具体做法是，枚举长度 l_0，然后枚举所有 l,r 满足 r-l+1 = l_0。

判断 l 到 r 形成的子串能否改造成满足要求的子串。

如果可以，那我们计算当前状态下，l_1 最多是多少。

算出来这个，自然也就可以得知同一个 l_0 对应的最大 l_1 是多少。

本题即迎刃而解。

现在解决这个问题：如何算出当前状态下，l_1 最多是多少。

设 l 到 r 的子串改造费用为 cost，那么 l 到 r 以外的字符还有 k-cost 次机会改造。

然后对于前后缀分别 dp，这个是 dp 初学者就会的，不用说了。

Code