← 返回比赛

已结束 GESP巅峰赛#28

← 上一题下一题 →

A6934 | $Alice 的分段游戏$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$（元素为正整数）。你需要把它划分成恰好 $k$ 个连续非空段，设第 $t$ 段为区间 $[L_t,R_t]$，并定义一段的代价为： $$ \mathrm{cost}(L,R)=\sum_{x}\binom{\#\{\, i\in[L,R]\mid a_i=x \,\}}{2}. $$ 也就是说，在同一段中，每个数的出现次数为 $c$ 就会贡献 $\binom{c}{2}$ 的代价。请最小化 $k$ 段代价之和： $$ \min \sum_{t=1}^{k}\mathrm{cost}(L_t,R_t), $$ 并输出该最小值。

输入格式

* 第一行两个整数 $n,k$。 * 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一个整数，表示最小总代价。

输入输出样例

输入 #1

5 2
1 2 1 2 1

输出 #1

输入 #2

6 3
1 1 1 2 2 3

输出 #2

数据范围 * $1\le n\le 2\times 10^5$； * $1\le k\le \min(n,20)$； * $1\le a_i\le 2\times 10^5$； * 答案不超过 $2^{63}-1$（使用 64 位有符号整数即可）。 测试点与数据范围 测试点规模约束$1\sim 6$$n\le 2\times 10^4,\ k\le 10$小规模、边界（全相等/全不同）$7\sim 20$$n\le 2\times 10^5,\ k\le 20$大规模，随机与构造混合压力 样例解释 - 样例一 : 解释：一种最优分法是 $[1,2,1]\ |\ [2,1]$。第一段中 $1$ 出现 $1$ 次贡献 $1$，第二段中没有重复对，总代价为 $1$。 - 样例二： 解释：可分为 $[1,1]\ |\ [1,2]\ |\ [2,3]$，总代价 $1$。

C++ 编辑器

输入

输出