题解

思路

记 $w(l,r)$ 为子段 $a_l,\ldots,a_r$ 中数值相同的元素对数。设 $dp_g(i)$ 表示把前 $i$ 个元素恰好划分成 $g$ 段的最小费用，则

$$dp_g(i)=\min_{g-1\le j<i}\{dp_{g-1}(j)+w(j+1,i)\}。$$

初始时 $dp_0(0)=0$，其余状态为无穷大。

做法

维护区间费用

维护当前区间以及每个数值在区间中的出现次数。向区间加入一个当前出现次数为 $c$ 的数值时，新增加 $c$ 对；删除一个出现次数为 $c$ 的数值时，减少 $c-1$ 对。因此，区间左右端点每移动一步，都能在常数时间内更新费用。

分治优化

区间费用满足四边形不等式，由此每一层动态规划的最优转移位置具有单调性。计算一段状态区间的中点时，只需枚举上一层给出的候选转移区间；取得最优位置后，左右两半分别只需搜索对应缩小后的候选区间。

每层分治中共有 $O(n\log n)$ 次候选考察。配合可移动的区间费用窗口，每次考察只需调整区间端点。

正确性说明

动态规划枚举了最后一个子段的左边界，所以每一种恰好划分成 $g$ 段的方案，都对应且只对应某次转移；取最小值后得到该状态的最优费用。区间费用维护中，加入或删除元素时更新的恰好是以该元素为一端的新生或消失的相同数值对，因此维护值始终等于当前区间真实费用。四边形不等式保证最优转移位置单调，分治只删除不可能成为最优位置的候选，不会漏掉最优转移。由层数归纳，最终的 $dp_k(n)$ 即所求最小费用。

复杂度

时间复杂度为 $O(kn\log n)$，空间复杂度为 $O(n)$。