HDU5009 Paint Pearls 分析

__ryp__ · 2024-02-13 16:40:16 · 个人记录

首先我们有一个朴素转移：设 f(i) 表示给前 i 个珍珠上色完的最少点数，那么 f(i) = \min\limits_{0\le j \le i} f(j) + \sigma^2(j+1,i)，其中 \sigma(i, j) 表示 [i, j] 的不同颜色数。

这个转移是 O(n^2) 的，我们考虑怎么优化。我们注意到：对于一个区间 [l, r]，我们存在平凡涂色方法，即一个一个涂色，这样的代价是 r - l + 1，即区间长。那么我们知道，每一个有意义的 f(i) \le i，于是 \sigma(j+1,i) \le \sqrt i，于是 j + 1 \le \sqrt i。我们可以直接认为 j \le \sqrt i，那么就变成了在 [\sqrt i, i] 上枚举最小的 j。

最终的转移方程是：