问题6808--愤怒的奶牛

6808: 愤怒的奶牛

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

【题目描述】

奶牛贝西设计了她认为下一款热门视频游戏:“愤怒的奶牛”。她认为这是完全原创的前提,即玩家用弹弓将一头牛射进一个一维场景,该场景由一组位于数字线上不同点的干草包组成;奶牛以足够的力量降落在干草捆上,导致干草捆爆炸,进而可能引发连锁反应,导致附近的其他干草捆爆炸。目标是用一头奶牛启动连锁反应,引爆尽可能多的干草包。

N个干草捆位于编号线上不同的整数位置x1x2、…、xN。如果奶牛被放在位置x处的干草捆上,该干草捆将以1的“爆炸半径”爆炸,这意味着1个单位距离内的任何其他干草捆也将被爆炸吞没。然后,这些相邻的捆本身发生爆炸(全部同时发生),每个捆的爆炸半径为2,因此这些爆炸可能会吞噬距离2个单位的其他未爆炸捆。在下一个时间步骤中,这些捆也会以爆炸半径3爆炸(全部同时爆炸)。通常,在时间t,一组干草捆将爆炸,每个干草捆的爆炸半径为t。被这些爆炸吞没的捆将在时间t+1爆炸,爆炸半径为t+1,依此类推。

请确定如果一头奶牛被投放到尽可能好的干草捆上以开始连锁反应,则可能发生爆炸的干草捆的最大数量。

【输入格式】(angry.in):

第一行输入包含N1N100). 其余的N行都包含整数x1xN(每个在01000000000范围内)。

【输出格式】(angry.out):

请输出单个奶牛可能导致爆炸的最大干草捆数。

【样例输入】:

6

8

5

6

13

3

4

【样例输出】:

5

【样例说明】

在本例中,将奶牛放在位置5处的干草捆上会导致位置46处的捆爆炸,每个捆的爆炸半径为2。这些爆炸又会导致位置38处的捆发生爆炸,每个包的爆炸半径均为3。但是,这些最终的爆炸强度不足以到达位置13处的捆。

来源/分类