304564: CF868F. Yet Another Minimization Problem
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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