冲突分段(Conflict Segmentation)

题目描述

对于一个序列，若存在一组 $(i, j)$ 使得 $i \neq j$ 且 $a_i = a_j$，我们称这两个数字之间产生了一次冲突。

现给定一个序列 $a_1, a_2, \cdots, a_n$，请将它分割为 $k$ 段，使得每一段内部的冲突次数之和最小。

输入格式

第一行：两个整数 $n$ 和 $k$，表示序列长度与需要分的段数

第二行：$n$ 个整数分别表示 $a_1, a_2, \dots, a_n$

输出格式

输出分段后，最少的冲突次数之和

样例输入 #1

5 2
3 5 3 1 4

样例输出 #1

0

说明: 序列分为 [3 5] [3 1 4]，没有冲突

样例输入 #2

10 2
2 3 2 3 2 3 2 3 2 3

样例输出 #2

8

说明: 序列分为 [2 3 2 3 2] , [3 2 3 2 3] ，两段内部冲突数均为 4

题目来源: 改编自 CF868F Yet Another Minimization Problem

数据范围

• 对于 30% 的数据，$1 \leq k \leq n \leq 1000$
• 对于 60% 的数据，$1 \leq k \leq n \leq 10000$
• 对于 100% 的数据，$1 \leq n \leq 10^5$，$k \leq 20$，$1 \leq a_i \leq n$

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐。

测试点分布