题解 P11233 [CSP-S 2024] 染色

· · 题解

貌似没看到这个思路。顺便把如何想到的过程也写上来了。

首先考虑 Task 3：\mathcal O(n^2) 能过。

考虑从左到右依次计算，设 f_{i,j,0/1} 表示前 i 个位置都染完色了，上一个与当前位置颜色不同的位置是 j，当前染红/蓝色的最大贡献，转移是简单的。

然后你会发现 0/1 这里并不需要，因为红蓝没有区别，所以状态变成了 f_{i,j}，转移为

\begin{aligned}f_{i+1,j}&\xleftarrow{\max}f_{i,j}+[a_i=a_{i+1}]a_i\\f_{i+1,i}&\xleftarrow{\max}f_{i,j}+[a_j=a_{i+1}]a_j\end{aligned}

我不会说我写完带 0/1 的部分后才发现没有必要并打表验证了一下的。

接着考虑 Task 5：值域 V 很小。

回头看上面的 dp 式子，你会发现 j 唯一的作用是提供了一个 a_j，那么为何不直接让 j 变成 a_j 呢？

设 f_{i,j} 表示前 i 个位置都染完色了，上一个与当前位置颜色不同的位置的值是 j 的最大贡献，转移为

\begin{aligned}f_{i+1,j}&\xleftarrow{\max}f_{i,j}+[a_i=a_{i+1}]a_i\\f_{i+1,{\color{red}a_i}}&\xleftarrow{\max}f_{i,j}+[{\color{red}j}=a_{i+1}]\color{red}j\end{aligned}

（不同处用红色标出）

最后考虑 Task 6：没有任何特殊性质。

注意到 Task 5 的做法可以很好地拓展，只要先把 f 滚动一下

\begin{cases}f_j&\xleftarrow{\max}f_j+[a_i=a_{i+1}]a_i\\f_{a_i}&\xleftarrow{\max}f_j+[j=a_{i+1}]j\end{cases}

再丢到线段树上即可。第一个转移是全局加，第二个转移是求单点最大值 + 全局最大值 + 单点取最大值。

注意：滚动的时候两个转移需要同时进行，可以通过先特判第二个转移会不会进行再进行第一个转移。

最后的最后，你会发现那四个操作都不用线段树，直接维护全局 tag 就好了，这样就是线性的了。

代码暂时没了。