Cowdependence

题目描述

农夫约翰有 $N$ 头奶牛（$1 \leq N \leq 10^5$）排成一列。 第 $i$ 头奶牛的标签为 $a_i$（$1 \leq a_i \leq N$）。如果一组奶牛满足：它们的标签都相同，并且组内任意两头奶牛之间相隔的奶牛数不超过 $x$（其中 $x$ 为 $[1,N]$ 范围内的整数），则它们可以组成一个友情小组。每头奶牛必须且只能属于一个友情小组。 对于每个 $x$ 从 $1$ 到 $N$，计算可能形成的友情小组的最少数量。

输入格式

第一行是一个整数 $N$。 第二行包含 $a_1 ... a_N$，表示每头奶牛的标签。

输出格式

对于每个 $x$ 从 $1$ 到 $N$，每行输出该 $x$ 下友情小组的最少数量。

9
1 1 1 9 2 1 2 1 1

7
5
4
4
4
4
4
3
3

提示

下面给出在 $x=1$ 和 $x=2$ 时，如何分配奶牛到友情小组以使小组数量最少的示例。每个字母对应一个不同的小组。 示例：

   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) 计分： 输入 2-3：$N\le 5000$ 输入 4-7：对所有 $i$，$a_i\le 10$ 输入 8-11：任一标签出现次数不超过 $10$ 次。 输入 12-20：无额外限制。 题目鸣谢：Chongtian Ma

标签: USACO|2024|Gold

来源

USACO|2024|Gold