本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-17 15:08:50

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

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