题解：P11233 [CSP-S 2024] 染色

cff_0102 · 2024-10-26 20:58:33 · 题解

2024/10/27 更新：增加了一些详细的描述。其实这个思路不难，同机房大佬也说“如果按我这个思路那么这题只有绿”，所以不应该花太多文字去讲，否则看起来更加混乱。但是因为有人问到了一些细节的问题，那就在这里补充一下。

设 dp_{i,j} 表示考虑前 i 个数，最后一个数涂的颜色是 j（j\in\{0,1\}）的最大得分。

对于第 i 位，它可能产生贡献，也可能不产生贡献。

如果它没有贡献，直接 dp_{i,0}=dp_{i,1}=\max(dp_{i-1,0},dp_{i-1,1})。

如果它有贡献，以 dp_{i,0} 为例：

那么前面一定也有一个染成了颜色 0 的相同的数，且这之间所有数都染成了颜色 1。

不难想到要选择前面的最后一个相同的数，因为如果不是最后一个，就可以在这两个数中间所有染成 1 的数里面找到另一个相同的数，把它也染 0 收益更大。

设前面这个相同的数的位置为 l（可以 O(n) 预处理出来），那么 dp_{i,0} 可以拆成三个部分计算：

• 位置在 1\sim l+1 的数产生的贡献，其中 l+1 染成了颜色 1。这个贡献即为 dp_{l+1,1}。此时不需要担心 l 没有被染成颜色 0 的问题，因为 dp_{l+1,1} 会选择最优策略，那么 l 此时是可以选择不和 l+1 染成同一个颜色的。
• 位置在 l+2\sim i-1 的数产生的贡献，这个贡献即为将 l+1\sim i-1 全部染成同一个颜色会产生的贡献。设 s_i 表示 1\sim i 染成同一个颜色的贡献，那么 l+1\sim i-1 全部染成同一个颜色会产生的贡献，或者说位置在 l+2\sim i-1 的数产生的贡献，就是 s_{i-1}-s_{l+1}。
• 位置在 i 的数产生的贡献，它等于 a_i。

因此如果第 i 个数产生了贡献，那么 dp_{i,0}=a_i+dp_{l_i+1,1}+s_{i-1}-s_{l_i+1}，这样转移是 O(1) 的。当然要特判一下 a_i=a_{i-1} 的情况，此时 dp_{i,0}=dp_{i-1,0}+a_i。dp_{i,1} 按同样的方法计算即可。

在产生贡献和不产生贡献的最大得分取 \max 即可，也就是 dp_{i,0}=\max(dp_{i-1,0},dp_{i-1,1},a_i+dp_{l_i+1,1}+s_{i-1}-s_{l_i+1})（如果 a_i\ne a_{i-1}），dp_{i,1} 同理。最后输出 \max(dp_{n,0},dp_{n,1})。

其实 dp_{i,0} 应该等于 dp_{i,1} 的来着，没必要开两倍空间，不过考场上也没想着优化了，反正能过就行。

代码见此。