Taming the Herd

题目描述

清晨时分，Farmer John 被木头碎裂的声音吵醒。 原来是奶牛们，它们又一次从牛棚里逃了出来！ Farmer John 对奶牛们每天早上的越狱已经厌烦透顶，于是他决定不再姑息：是时候强硬起来了。他在牛棚墙上钉了一个计数器，用来记录距离上一次越狱已经过去了多少天。因此，如果某天早上发生了越狱，那么当天计数器会显示为 $0$；如果最近一次越狱发生在 $3$ 天之前，那么计数器会显示为 $3$。Farmer John 认真地每天记录一次计数器的数值。 一年结束了，Farmer John 准备开始清算。 “奶牛们要付出代价！”他说。但他记录的日志似乎有些不对劲…… Farmer John 想知道自从他开始记录日志以来，一共发生了多少次越狱。然而，他怀疑奶牛篡改了他的日志，而他唯一确定的是：他开始记录日志的那一天正好发生了越狱。请你帮助他确定：对于从开始记录以来可能发生的每一种越狱次数，至少需要篡改多少条日志记录，才能与某种符合该越狱次数的情况一致。

输入格式

第一行包含一个整数 $N$ ($1 \leq N \leq 100$)，表示自 Farmer John 开始记录奶牛越狱计数器以来经过的天数。 第二行包含 $N$ 个用空格分隔的整数。第 $i$ 个整数是一个非负整数 $a_i$（不超过 $100$），表示第 $i$ 天计数器的值为 $a_i$，除非奶牛篡改了当天的日志记录。

输出格式

输出应包含 $N$ 行整数，每行一个。 第 $i$ 行的整数应为：在所有可能的、恰好发生 $i$ 次越狱的越狱序列中，使得与该序列不一致的日志记录条数的最小值。

6
1 1 2 0 0 1

4
2
1
2
3
4

提示

如果只发生了 1 次越狱，那么正确的日志应为 0 1 2 3 4 5，与给定日志相比有 4 个条目不同。 如果发生了 2 次越狱，那么正确的日志可能为 0 1 2 3 0 1，与给定日志相比有 2 个条目不同。在这种情况下，越狱发生在第 1 天和第 5 天。 如果发生了 3 次越狱，那么正确的日志可能为 0 1 2 0 0 1，与给定日志相比只有 1 个条目不同。在这种情况下，越狱发生在第 1 天、第 4 天和第 5 天。 以此类推。 题目致谢：Brian Dean 和 Dhruv Rohatgi

标签: USACO|2018|Gold

来源

USACO|2018|Gold