CF1527E.Partition Game

You are given an array $a$ of $n$ integers. Define the cost of some array $t$ as follows:

$$cost(t) = \\sum\_{x \\in set(t) } last(x) - first(x),$$

where $set(t)$ is the set of all values in $t$ without repetitions, $first(x)$, and $last(x)$ are the indices of the first and last occurrence of $x$ in $t$, respectively. In other words, we compute the distance between the first and last occurrences for each distinct element and sum them up.

You need to split the array $a$ into $k$ consecutive segments such that each element of $a$ belongs to exactly one segment and the sum of the cost of individual segments is minimum.

给你一个包含 $n$ 个整数的数组 $a$。定义某个数组 $t$ 的代价如下：

$$cost(t) = \sum\_{x \in set(t) } last(x) - first(x),$$

其中 $set(t)$ 表示数组 $t$ 中所有不同元素构成的集合，$first(x)$ 和 $last(x)$ 分别表示元素 $x$ 在 $t$ 中首次出现和末次出现的下标（从 1 开始计数）。换言之，我们对每个不同元素计算其首次与末次出现位置之间的距离，并将所有这些距离求和。

你需要将数组 $a$ 划分为 $k$ 个连续的子数组（段），使得 $a$ 中的每个元素恰好属于其中一个段，且各段的代价之和最小。

The first line contains two integers $n$, $k$ ($1 \le n \le 35\,000$, $1 \le k \le \min(n,100)$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

第一行包含两个整数 $n$、$k$（$1 \le n \le 35\,000$，$1 \le k \le \min(n,100)$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。

Output the minimum sum of the cost of individual segments.

输出各段成本的最小总和。

In the first example, we can divide the array into $[1,6,6,4]$ and $[6,6,6]$. Cost of $[1,6,6,4]$ will be $(1-1) + (3 - 2) + (4-4) = 1$ and cost of $[6,6,6]$ will be $3-1 = 2$. Total cost would be $1 + 2 = 3$.

In the second example, divide the array into $[5,5],[5],[5,2,3]$ and $[3]$. Total Cost would be $1 + 0 + 0 + 0 = 1$.

在第一个例子中，我们可以将数组划分为 $[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$。