AtCoder Beginner Contest 345 E - Colorful Subsequence 题解

题意

有 $N$ 个球，每一个球有一个颜色 $C_i$ 和价值 $V_i$，现在要删除其中的 $K$ 个球，使得剩下的球没有相邻的两个球颜色相等。求剩下的球的最大价值总和。

数据范围

• $1\leq K < N \leq 2\times 10^5$
• $K \leq 500$

思路

考虑 dp。

设计状态 $f_{i,j}$ 代表不删除第 $i$ 个球，在前面删除 $j$ 个球时最大的价值总和。

则 $f_{i,j}$ 一定由前面的第 $k$ 个球删除 $(k,i)$ 之间的全部 $i-k-1$ 个球转移而来，状态转移方程为 $f_{i,j}=\max\{f_{k,j-(i-k-1)}\}(j\leq K,i-j-1\leq k<i,c_i≠c_k)+v_i$。

这样转移是 $\mathcal{O}(nk^2)$ 的，实测会超时，考虑优化。

优化

发现转移过来的状态里，第一维和第二维的差总是相等，于是我们可以维护一个 $g_x=\max\{f_{j,j-x}\}$，$f_{i,j}$ 的转移就可以优化到 $\mathcal{O}(1)$。

当时把我卡住的难点在于如何保证当前最优解 $g_{i-j}$ 的颜色与当前的 $c_i$ 不同。

方法则是维护两个颜色不同的最优解和次优解，这样如果当前的 $c_i$ 与最优解的颜色相同，就可以从次优解转移过来。

细节详见代码。