问题 D: 青蛙跳 问题 D: 青蛙跳
时间限制: 1 Sec 内存限制: 256 MB
提交: 2 解决: 1
[提交][状态][命题人:]题目描述
有一只青蛙在池塘的莲叶上跳跃。
有 30000 个莲叶从左到右排成一排,相邻莲叶间的距离为 1 米。其中有 n 个水珠在莲叶上。
若青蛙跳到带有水珠的莲叶上,会将水珠溅起,在阳光下形成短暂的彩虹。一个莲叶上可能有多个水珠。
初始青蛙在最左边的岸上,第一个莲叶距离岸边 1 米,每次从左到右跳跃到一个莲叶上。
第一次向右跳跃 x 米,跳到第 x 个莲叶上。接下来每一次跳跃,若上一次跳了 c 步,则这次可以跳跃 c,c-1 或 c+1 步。特别的,若上一次跳了 1 米,则这次不能跳 0 米。
求最多会溅起几个水珠。
输入
第一行包含两个正整数 n,x (1≤n,x≤3·10^4) ,表示带水珠的莲叶数和第一次跳跃距离。
接下来 n 行,第 i 行包含一个整数 p[i] (d≤p[1]≤p[2]≤...≤p[n]≤30000) ,表示第 i 个水珠所在的莲叶和岸边的距离。
输出
输出有一个整数,表示最多会溅起的水珠数。
提示
样例解释
在第一组样例中,最优方案为 0→10(+1)→19→27(+2)→... ,总计 3 个水珠。
在第二组样例中,最优方案为 0→8→15→21→28(+1)→36(+1)→45(+1)→55(+1)→66(+1)→78(+1)→... ,总计 6 个水珠。
在第三组样例中,最优方案为 0→7→13→18(+1)→24(+2)→30(+1)→... ,总计 4 个水珠。
[提交][状态]