分组游戏

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的整数数组 $a$。对任意非空数组 $t$，定义

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

其中 $\operatorname{first}(x)$ 和 $\operatorname{last}(x)$ 分别是 $x$ 在 $t$ 中第一次和最后一次出现的位置。

请把 $a$ 恰好划分成 $k$ 个连续非空段，使所有段的代价之和最小。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示最小总代价。

样例输入 1

7 2
1 6 6 4 6 6 6

样例输出 1

3

样例输入 2

7 4
5 5 5 5 2 3 3

样例输出 2

1

数据范围

对于所有数据，$1\le n\le35000$，$1\le k\le\min(n,100)$，$1\le a_i\le n$。

子任务编号	分值	特殊限制
1	30	$n\le18$，$k\le6$
2		$n\le1000$，$k\le30$
3	40	无特殊限制