问题 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 个水珠所在的莲叶和岸边的距离。

输出

输出有一个整数,表示最多会溅起的水珠数。
样例输入
Copy
样例1:
4 10
10
21
27
27

样例2:
8 8
9
19
28
36
45
55
66
78

样例3:
13 7
8
8
9
16
17
17
18
21
23
24
24
26
30
样例输出
Copy
样例1:
3

样例2:
6

样例3:
4

提示

样例解释
在第一组样例中,最优方案为 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 个水珠。
[提交][状态]