本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$。

最终的转移方程是：

$$f(i)=\min\limits_{\sqrt i\le j\le i} f(j)+\sigma^2(j+1,i)$$