#PU1449. USACO 2024 December Contest, Gold — Problem 1. Cowdependence
USACO 2024 December Contest, Gold — Problem 1. Cowdependence
USACO 2024 December Contest, Gold — Problem 1. Cowdependence
题目描述
Farmer John's cows have been arranged into a line. The th cow has label (). A group of cows can form a friendship group if they all have the same label and each cow is within cows of all the others in the group, where is an integer in the range . Every cow must be in exactly one friendship group. For each from to , calculate the minimum number of friendship groups that could have formed.
输入格式
The first line consists of an integer . The next line contains , the labels of each cow.
输出格式
For each from to , output the minimum number of friendship groups for that on a new line.
数据范围
Inputs 2-3: Inputs 4-7: for all Inputs 8-11: No label appears more than times. Inputs 12-20: No additional constraints. Problem credits: Chongtian Ma
样例
样例 1
9
1 1 1 9 2 1 2 1 1
7
5
4
4
4
4
4
3
3
Here are examples of how to assign cows to friendship groups for $x=1$ and $x=2$
in a way that minimizes the number of groups. Each letter corresponds to a
different group.
Example:
1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G (7 groups)
x = 1: A A B C D E F G G (7 groups, alternative grouping)
x = 2: A A A B C D C E E (5 groups)
x = 2: A A A B C D C D E (5 groups, alternative grouping)