#7100. 冲突分段

冲突分段

题目描述

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

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

输入格式

第一行:两个整数 nnkk,表示序列长度与需要分的段数 第二行:nn 个整数分别表示 a1,a2,,ana_1,a_2,\dots,a_n

输出格式

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

5 2
3 5 3 1 4
0

样例解释 1

序列分为[3 5] [3 1 4],没有冲突

10 2
2 3 2 3 2 3 2 3 2 3
8

样例解释 2

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

数据范围

  • 对于 30%30\% 的数据,1kn10001 \leq k \leq n \leq 1000
  • 对于 60%60\% 的数据,1kn100001 \leq k \leq n \leq 10000
  • 对于 100%100\% 的数据,1n1051 \leq n\leq 10^5k20k\leq 201ain1\le a_i\le n