题解

思路

固定最终的一段连续零，设其长度为 $x$。把这段中的所有 1 翻成 0 后，剩余翻转次数应全部用于在该段左侧或右侧制造最长连续一，因为两段不能相交。

对每个翻转预算 $c$，用双指针预处理：任意前缀中最多翻转 $c$ 个 0 时可得到的最长连续一；反转字符串后再做一次，就得到任意后缀的同类信息。

做法

枚举零段 $[l,r]$。由前缀和得到把它变成全零所需翻转的 1 数量 $cost$。若 $cost\le k$，令 $rem=k-cost$，则与它不相交的最长一段是左前缀表和右后缀表中的较大值。用它更新 best[r-l+1]。best[0] 则是不指定零段时，整串中最多翻转 $k$ 个 0 所得的最长一段。

最后对于每个 $a=1,\ldots,n$，枚举零段长度 $x$，取

当 $n\le12$ 时可以枚举翻转后的所有二进制串；当 $k=0$ 时直接计算原串最长零段和最长一段。

正确性说明

任意可行最终字符串中，取一段最长零段。枚举会选到相同区间，并准确扣除把它变为全零的翻转次数。最长一段必与该零段不相交，因此完全位于左侧或右侧，预处理表会给出至少同样长的一段。反之，枚举选定的零段与预处理得到的一段互不相交，二者翻转总数不超过 $k$，所以每个候选值都可实现。两边互相包含，取最大值即为答案。

复杂度

满分算法每组时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$；总规模约束保证所有测试组可在该复杂度内处理。