题意

有 NN 个球，每一个球有一个颜色 CiC_i 和价值 ViV_i，现在要删除其中的 KK 个球，使得剩下的球没有相邻的两个球颜色相等。求剩下的球的最大价值总和。

数据范围

  • 1≤K<N≤2×1051\leq K < N \leq 2\times 10^5
  • K≤500K \leq 500

思路

考虑 dp。

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

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

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

优化

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

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

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

细节详见代码。