9688

原题链接:P9688 Colo. 很显然，能够共存的颜色一定不会相交，所以可以记录每个颜色最左边的位置和最右边的位置，我们对于每个颜色只考虑，这个颜色左边的可以和这个颜色共存的额颜色 用f[i][j]表示当前考虑i这种颜色，选i这种颜色，然后在i这种颜色之前（包括这种颜色）一共选了j种颜色的最大价值 ......

题目传送门 思路： 设有两个颜色 \(x_1 x_2\) ，两端分别为 \(l_1\) \(r_1\) ， \(l_2\) \(r_2\)。通过观察可以发现，若满足 \(x_1<x_2\) 且 \(r_1 > l_2\) 则 \(x_1 x_2\) 一定是单调不下降的。 那么我们可以先预处理出一个颜 ......

\(Solution\) 考虑 dp。 观察数据范围，\(n,k\leq 500\) 的数据几乎明示了同阶下 \(\Theta(n^3)\) 的算法了。那么直接往这里考虑。 设 \(f_{i,j}\) 为当前是第 \(i\) 中颜色，且已经选了 \(j\) 种颜色的最大值。 那么有以下转移方程： \ ......