A14338 | 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), $$ </p><p>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.</p><p>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.

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$ ).

Output the minimum sum of the cost of individual segments.