← 返回题目

题库练习 Yet Another Minimization Problem

← 上一题下一题 →

A11197 | $Yet Another Minimization Problem$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输入 #2

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

输出 #2

输入 #3

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

输出 #3

C++ 编辑器

输入

输出