CF1527E Partition Game

给定一个长度为 $n$ 的整数数组 $a$。定义某个数组 $t$ 的代价如下： $$ cost(t) = \sum_{x \in set(t)} last(x) - first(x), $$ 其中 $set(t)$ 表示 $t$ 中所有不同元素组成的集合，$first(x)$ 和 $last(x)$ 分别表示 $x$ 在 $t$ 中第一次和最后一次出现的位置的下标。换句话说，对于每个不同的元素，计算其在 $t$ 中第一次和最后一次出现位置的距离，然后将这些距离相加。 你需要将数组 $a$ 划分为 $k$ 个连续的区间，使得每个元素恰好属于一个区间，并且所有区间的代价之和最小。

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 35000$，$1 \le k \le \min(n,100)$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。

输出所有区间代价之和的最小值。

在第一个样例中，可以将数组划分为 $[1,6,6,4]$ 和 $[6,6,6]$。$[1,6,6,4]$ 的代价为 $(1-1) + (3-2) + (4-4) = 1$，$[6,6,6]$ 的代价为 $3-1 = 2$。总代价为 $1 + 2 = 3$。 在第二个样例中，可以将数组划分为 $[5,5]$、$[5]$、$[5,2,3]$ 和 $[3]$。总代价为 $1 + 0 + 0 + 0 = 1$。 由 ChatGPT 4.1 翻译