Yet Another Minimization Problem

题目描述：给定一个序列 $a$，要把它分成 $k$ 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。 输入格式：第一行输入 $n$（序列长度）和 $k$（需分子段数）。接下来一行有 $n$ 个数，第 $i$ 个数表示序列的第 $i$ 个元素 $a_i$。 输出格式：输出一个数，费用和的最小值。 $2 \leq n \leq 10^5$，$2 \leq k \leq \min(n,20)$，$1 \leq a_i \leq n$ 。

You are given an array of $ n $ integers $ a_{1}...\ a_{n} $ . The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given array into $ k $ non-intersecting non-empty subsegments so that the sum of their costs is minimum possible. Each element should be present in exactly one subsegment.

The first line contains two integers $ n $ and $ k $ ( $ 2<=n<=10^{5} $ , $ 2<=k<=min\ (n,20)) $ — the length of the array and the number of segments you need to split the array into. The next line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=n $ ) — the elements of the array.

Print single integer: the minimum possible total cost of resulting subsegments.

7 3
1 1 3 3 3 2 1

1

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

8

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

9

In the first example it's optimal to split the sequence into the following three subsegments: $ [1] $ , $ [1,3] $ , $ [3,3,2,1] $ . The costs are $ 0 $ , $ 0 $ and $ 1 $ , thus the answer is $ 1 $ . In the second example it's optimal to split the sequence in two equal halves. The cost for each half is $ 4 $ . In the third example it's optimal to split the sequence in the following way: $ [1,2,2,2,1] $ , $ [2,1,1,1,2] $ , $ [2,1,1] $ . The costs are $ 4 $ , $ 4 $ , $ 1 $ .