#P15685. [Bulgarian2022训练营]hotel酒店

[Bulgarian2022训练营]hotel酒店

题目描述

Kyusho 上一次给选手安排房间时表现得不太好,于是他决定再试一次。这次他认为,最好让参赛者彼此多认识一些人,所以他希望每个房间中来自不同城市的人尽可能多。

共有 NN 名参赛者,编号为 11 到 NN。第 ii 名参赛者来自城市 cic_i。

这些参赛者需要被安排到 KK 个房间中。由于所有人已经在前台排好队,Kyusho 决定不改变他们的相对顺序:他会把前 T1T_1 人安排到第一个房间,把接下来的 T2T_2 人安排到第二个房间,依此类推,直到把最后 TKT_K 人安排到第 KK 个房间。

注意,必须满足:

T1+T2+⋯+TK=NT_1+T_2+\cdots+T_K=N

并且每个房间至少有一人,即 Ti≥1T_i\ge 1。

第 ii 个房间的熟识度 FiF_i 定义为这个房间中参赛者来自的不同城市数量。

Kyusho 希望最大化

F1+F2+⋯+FK.F_1+F_2+\cdots+F_K.

请编写程序 hotel,求出这个最大值。

输入格式

第一行包含两个正整数 N,KN,K,分别表示参赛者数量和房间数量。

第二行包含 NN 个整数 cic_i,表示每名参赛者来自的城市。

输出格式

输出一行一个整数,表示 F1+F2+⋯+FKF_1+F_2+\cdots+F_K 的最大可能值。

数据范围

  • 1≤N≤50001\le N\le 5000;
  • 1≤K≤min⁡(N,500)1\le K\le \min(N,500);
  • 1≤ci≤N1\le c_i\le N。

子任务

子任务 分值 NN KK cic_i
1 15 ≤5000\le 5000 =2=2 ≤N\le N
2 40 ≤500\le 500 ≤500\le 500
3 35 ≤5000\le 5000 ≤10\le 10
4 10 ≤N\le N

某个子任务得分,要求通过该子任务中的所有测试点。

样例 1

输入

4 1
1 2 2 1

输出

2

解释

取 T1=4T_1=4。

样例 2

输入

7 2
1 3 3 1 4 4 4

输出

5

解释

一种最优划分为 T1=2,T2=5T_1=2,T_2=5。

样例 3

输入

8 3
7 7 8 7 7 8 1 7

输出

6

解释

一种最优划分为 T1=3,T2=3,T3=2T_1=3,T_2=3,T_3=2。