题解

思路

分别计算“尽量把所有字母变成小写”和“尽量把所有字母变成大写”时剩余的错误字母数，取较小值即可。固定目标大小写后，令 $a_i=1$ 表示第 $i$ 个字母与目标不同。

所有操作都改成目标大小写不会让答案变差。每次操作相当于覆盖至多 $l$ 个尚未处理的位置；即使靠近边界或与其他操作重叠，也总能把所选区段扩展成一个合法的长度 $l$ 区间，扩展只会额外消除错误字母。

子任务 1 可以枚举至多 $k$ 个区间的所有组合，直接统计未被覆盖的错误位置。

子任务 2 使用分层动态规划。设前缀和为 $P$，$f_j(i)$ 表示前 $i$ 个位置使用至多 $j$ 次操作能够覆盖的最大错误数，则

$$f_j(i)=\max\left(f_j(i-1),f_{j-1}(q)+P_i-P_q\right),\qquad q=\max(0,i-l).$$

答案为错误总数减去 $f_k(n)$。

满分算法去掉操作次数这一维。给每次操作附加整数代价 $w$，令 $dp_i$ 为处理完前 $i$ 个位置的最小“未覆盖错误数加总代价”，并在代价相同时选择操作次数更少的方案。转移有两种：

• 不覆盖第 $i+1$ 个位置，代价增加 $a_{i+1}$；
• 使用一次操作覆盖接下来的至多 $l$ 个位置，代价增加 $w$。

随着 $w$ 增大，最优方案使用的操作次数单调不增。因此二分最小的 $w$，使最优方案使用次数不超过 $k$。若这个 $w$ 为零，答案为零；否则由拉格朗日松弛的离散凸性，固定目标下的答案是

$$dp_n-wk.$$

对两种目标大小写各计算一次。

做法

1. 把字符串转换成针对某一种目标大小写的 $0/1$ 数组。
2. 二分操作代价 $w$。
3. 每次检查用一遍线性 DP，同时维护最小代价和对应的最少操作次数。
4. 用 $dp_n-wk$ 还原至多 $k$ 次操作的最优值。
5. 对全小写和全大写两种目标取最小值。

复杂度

子任务 1 的时间复杂度为 $O\!\left(n\sum_{j=0}^{k}\binom{n-l+1}{j}\right)$，空间复杂度为 $O(n)$。

子任务 2 的时间复杂度为 $O(nk)$，空间复杂度为 $O(n)$。

满分算法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。