← 返回题目列表

Codeforces · 1527/E

E. 分区游戏

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。定义某个数组 $$$t$$$ 的成本如下:

$$$$$$cost(t) = \sum_{x \in set(t) } 最后一个(x) - 第一个(x),$$$$$$

其中 $$$set(t)$$$ 是 $$$t$$$ 中没有重复的所有值的集合,$$$first(x)$$$ 和 $$$last(x)$$$ 分别是 $$$x$$$ 在 $$$t$$$ 中第一次和最后一次出现的索引。换句话说,我们计算每个不同元素的第一次出现和最后一次出现之间的距离并将它们相加。

您需要将数组 $$$a$$$ 拆分为 $$$k$$$ 连续段,使得 $$$a$$$ 的每个元素恰好属于一个段,并且各个段的成本之和最小。

输入

第一行包含两个整数 $$$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$$$)。

输出

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

示例

输入 #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,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$$$。