#7100. 冲突分段
冲突分段
题目描述
对于一个序列,若存在一组 使得 且 ,我们称这两个数字之间产生了一次冲突。
现给定一个序列 ,请将它分割为 段,使得每一段内部的冲突次数之和最小。
输入格式
第一行:两个整数 和 ,表示序列长度与需要分的段数 第二行: 个整数分别表示
输出格式
输出分段后,最少的冲突次数之和
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
数据范围
- 对于 的数据,
- 对于 的数据,
- 对于 的数据,,,