Angry Cows

题目描述

奶牛 Bessie 设计了一款她认为会成为下一款热门的电子游戏：“Angry Cows”。其设定（她相信完全原创）是：玩家用弹弓把一头奶牛射入一个一维场景，场景由若干个位于数轴不同位置的干草堆组成；奶牛落在某个干草堆上并以足够的冲击力使其爆炸，爆炸可能引发连锁反应，使附近更多干草堆爆炸。目标是只用一头奶牛引发连锁反应，尽可能引爆更多的干草堆。

数轴上有 $N$ 个干草堆，分别位于互不相同的整数位置 $x_1, x_2, \ldots, x_N$。如果把奶牛发射到位置 $x$ 的某个干草堆上，该干草堆会以“爆炸半径”1 发生爆炸，即距离其 1 个单位以内的所有其他干草堆也会被爆炸波及。这些相邻的干草堆随后也会爆炸（同时发生），每个的爆炸半径为 2，因此这些爆炸可能波及到距离它们 2 个单位以内、尚未爆炸的干草堆。在下一个时间步，这些干草堆也会爆炸（同时发生），爆炸半径为 3。一般而言，在时间 $t$ 会有一组干草堆发生爆炸，每个的爆炸半径为 $t$。被这些爆炸波及的干草堆会在时间 $t+1$ 发生爆炸，爆炸半径为 $t+1$，依此类推。

请你计算：如果只发射一头奶牛，并选择最佳的起始干草堆来触发连锁反应，最多能引爆多少个干草堆。

输入格式

第一行输入 $N$（$1 \leq N \leq 100$）。接下来的 $N$ 行每行包含一个整数 $x_1 \ldots x_N$（每个都在范围 $0 \ldots 1,000,000,000$ 之内）。

输出格式

输出一头奶牛最多可以引爆的干草堆数量。

6
8
5
6
13
3
4

5

提示

在该示例中，将奶牛发射到位置 5 的干草堆上会使位置 4 和 6 的干草堆爆炸，它们的爆炸半径均为 2。这些爆炸又会使位置 3 和 8 的干草堆爆炸，它们的爆炸半径均为 3。然而，这最后的爆炸强度不足以波及位置 13 的干草堆。 题目贡献：Brian Dean

标签: USACO|2016|Bronze

来源

USACO|2016|Bronze