题解：P12667 [KOI 2023 Round 2] 傻瓜锁

· · 题解

这个题似乎挺套路的，但是我做题太少，没见过。

首先有一个 55 分的 ddp 做法，但是这个矩阵没啥性质，优化不了。

考虑答案的形态，形如 aaabbcccddd…… 的形式，我们将不同字符的分界处称作分界点。对于第 j 个分界点，设位置为 p，我们需要令 i\le p 的全部修改至小于等于 j，令 i>p 的修改至大于 j。

对于这种限制我们通常转 0/1。具体地，令大于 j 的为 1，小于等于的为 0，对于分界点 j 的贡献就是下标小于 p 的 1 的数量加上后面的 0 的数量，容易发现把所有分界点的贡献加起来就是正确的贡献。

发现对于一个分界点，其他分界点似乎对他没什么影响？确实分界点相对独立，考虑我们已经处理了前 j-1 个分界点，大小为 j 的不会因为新的分界点加入，就改变 j-1 这种颜色的位置，换句话说，如果发生了挤压，是一定可以换成保持前面最优分界点的。

用线段树维护最优分界点的代价，具体地，维护区间改成 1 的代价，0 的代价，分界点在这个区间内的代价就行了。

代码很好写，不放了。

对于这种套路，有人把他称作决策单调性，我觉得不如看做决策点（分界点）的延迟决策。