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.

输入输出样例

输入样例 #1

7 3
1 1 3 3 3 2 1

输出样例 #1

1

输入样例 #2

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

输出样例 #2

8

输入样例 #3

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

输出样例 #3

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 $ .