← 返回题目列表

Codeforces · 868/F

F. 又一个最小化问题

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

给定一个由 n 个整数 a1...an 组成的数组。子段的成本是子段内包含相同元素的不同索引的无序对的数量。将给定数组拆分为 k 个不相交的非空子段,以使它们的成本总和尽可能最小。每个元素应该恰好出现在一个子段中。

输入

第一行包含两个整数 n 和 k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20)) — 数组的长度以及需要将数组分割成的段数。

下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n) — 数组的元素。

输出

打印单个整数:结果子段的最小可能总成本。

示例

输入 #1

7 3
1 1 3 3 3 2 1

输出 #1

1

输入 #2

10 2
1 2 1 2 1 2 1 2 1 2

输出 #2

8

输入 #3

13 3
1 2 2 2 1 2 1 1 1 2 2 1 1

输出 #3

9

注意

在第一个示例中,最好将序列分为以下三个子段:[1]、[1, 3]、[3, 3, 2, 1]。成本为 0、0 和 1,因此答案为 1。

在第二个示例中,最好将序列分成相等的两半。每一半的成本是4。

在第三个示例中,最好按以下方式分割序列:[1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]。成本为 4, 4, 1。