分治优化

例题 #1 Partition Game

题面翻译

\(hater\)扔给你一个长度为\(n\)序列，定义其中一个连续子序列\(t\)的代价为：

\(cost(t)=\sum_{x\in set(t)}last(x)−first(x)\)

其中\(set(t)\)表示该子序列的元素集合，\(last(x)\)表示\(x\)在该子序列中最后一次出现的位置，\(first(x)\)表示\(x\)在该子序列中第一次出现的位置。

也就是说一个连续子序列的贡献为对于其中每种元素最后一次出现的位置与第一次出现的位置的下标差的和。

现在你要把原序列划分成\(k\)个连续子序列，求最小代价和。

其中\(1\leq n\leq35000,1\leq k\leq min(n,100),1\leq a_i \leq n\)。