P2943 [USACO09MAR] Cleaning Up G

题目描述

给定一个有 $N$ 个数的序列 $a_i$ 。

现在要把序列分成若干段，定义每段的费用为：若这段里有 $k$ 个不同的数，那费用为 $k ^2$ 。

求最小总费用。

输入格式

第一行两个整数： $N \ M(1 \le M \le N \le 40000)$ 。

下来 $N$ 个整数 $a_i(1 \le a_i \le M)$

输出格式

一行一个整数，即最小总费用。

输入输出样例 #1

输入 #1

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

输出 #1

11

说明/提示

1 | 2 | 1 | 3 | 2 2 | 3 4 3 4 3 | 1 | 4

总费用为：$11$