#PU1449. USACO 2024 December Contest, Gold — Problem 1. Cowdependence

    ID: 1301 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases枚举

USACO 2024 December Contest, Gold — Problem 1. Cowdependence

USACO 2024 December Contest, Gold — Problem 1. Cowdependence

题目描述

Farmer John's NN (1≤N≤105)(1 \leq N \leq 10^5) cows have been arranged into a line. The iith cow has label aia_i (1≤ai≤N1 \leq a_i \leq N). A group of cows can form a friendship group if they all have the same label and each cow is within xx cows of all the others in the group, where xx is an integer in the range [1,N][1,N]. Every cow must be in exactly one friendship group. For each xx from 11 to NN, calculate the minimum number of friendship groups that could have formed.

输入格式

The first line consists of an integer NN. The next line contains a1...aNa_1 ... a_N, the labels of each cow.

输出格式

For each xx from 11 to NN, output the minimum number of friendship groups for that xx on a new line.

数据范围

Inputs 2-3: N≤5000N\le 5000 Inputs 4-7: ai≤10a_i\le 10 for all ii Inputs 8-11: No label appears more than 1010 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)