题意
给定 \(n\) 个球，每个球有颜色 \(C_i\)，价值 \(V_i\)。
你需要删除恰好 \(k\) 个小球，使得剩余的小球没有相邻颜色相同且价值最大。
求这个价值。
\(k \le 500, n \le 2 \times 10 ^ 5\)
Sol
考虑一个平凡的 dp。
\(f_{i, j}\) 表示最后剩了 \(i\)，当前留下了 \(j\) 个的最大价值。
\[f_{i, j} = \max_{p < i, C_p \neq C_i} f_{p, j - 1} + V_i \]注意到对于每一个 \(j\) 来说，可以有贡献的 \(i\) 当前仅当满足：\(j \le i, i \le j + k\)。因此状态数为 \(nk\)。
考虑加速转移，容易想到先枚举 \(j\)，然后在转移的过程中更新 \(j - 1\) 对当前的答案。
记录 \(j - 1\) 的最大值、最大值的颜色、次大值即可。
标签：Comparison,le,最大值,小球,Points,ABC344G From： https://www.cnblogs.com/cxqghzj/p/18089910