[CF868-F] Yet Another Minimization Problem
时间限制：1000MS 内存限制：262144KB
难度：\(6.0\)
-
题目描述
有 \(n\) 个正整数构成序列 \(a\) ，定义一个区间 \([l, r]\) 的代价为 满足 \(l \leq i, j \leq r\) 并使得 \(a_i=a_j\) 的无序对 \([i, j]\) 的数量。
现要把 \(a\) 分成 \(k\) 个互不相交且不为空的连续的区间，求出在所有分法中，分出区间的最小代价和是多少。
-
输入格式
第一行，两个正整数 \(n, k\) 。
第二行，序列 \(a\) ，共 \(n\) 个元素，用一个空格隔开。
-
输出格式
一个整数，表示在所有分法中，分出区间的最小代价和。
-
样例输入
|
1 2 |
7 3 1 1 3 3 3 2 1 |
-
样例输出
|
1 |
1 |
-
样例说明
一种可能的分法为 \([1], [1, 3], [3, 3, 2, 1]\) 。
第一个区间的代价为 \(0\) ，第二个区间的代价为 \(0\) ，第三个区间的代价为 \(1\) ，最小代价和为 \(1\) 。
（其他样例见原题
-
数据范围
对于 \(10\%\) 的数据，\(2 \leq n \leq 20\) 。
对于 \(40\%\) 的数据，\(2 \leq n \leq 1000\) 。
对于 \(100\%\) 的数据，\(2 \leq n \leq 10^5\) ，\(2 \leq k \leq min\{20,n\}\) 。
保证 \(1 \leq a_i \leq n\) 。
\(Source\): CF868-F …
