[dp] P2135 方块消除

_Cheems · 2024-07-03 14:09:52 · 题解

挺好一道区间 dp。题解区写的都啥啊，根本看不懂。

首先假如相邻颜色段颜色相等，我们就将其合并，记颜色为 a_i，数量为 b_i。可以证明，我们一定不会把一个颜色段拆开来操作，因为价值是平方，有 (x+y)^2\ge x^2+y^2。

容易想到定义 g_{i,j} 表示消除 [i,j] 内的所有颜色段的最大价值。转移就是枚举段内颜色，将所有该颜色的单独拎出来最后一起操作，然后价值就是其余段的 g 之和以及该颜色数量的平方。

但这是错误的！因为不一定要把所有该颜色的都放在一起最后消掉，我们可以选取一部分让它先被消掉以满足某些需求。

例如：

5
1 2 1 2 1
4 6 1 6 4

可以先消中间那段 1，使得两段 2 合并，最后合并两端的 1。这样更优。

如何解决？不妨将所有选取方案（即选择放在最后消掉的元素）分为两类：r 被选和不被选。假如 r 不被选，那么正常进行区间合并即可枚举到所有情况。假如 r 被选，必须记录当前被选元素的总数（\sum b）。