A4805 | 跳格子
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
假期到了，你和你的同伴们玩一个跳格子游戏。
这个游戏由$30001$个格子组成。 这些格子沿一条线均匀分布，从西到东编号为$0$到$30000$，每个格子的距离都是单位长度。
众所周知，格子游戏肯定要找宝藏。格子游戏一共藏有$n$颗宝石，第$i$颗宝石位于编号为$a_i$的格子上。
现在游戏的起点为$0$号格子，凭借着超强的跳跃能力，你会按照以下方式进行跳跃：
- 首先，你会从$0$号格子跳到$d$号格子。
- 第二步开始，你将按照以下规则继续跳跃： 令$l$为上一次跳跃的长度，那么这一次跳跃，你向前跳跃的长度只能是$l - 1$、$l$ 或 $l + 1$。限制：一次跳跃的长度必须为正，即当$l = 1$时，你不能进行长度为$0$的跳转。你随时可以自己决定结束游戏。
如果你到了一个有宝石的格子，你会收集这个格子上的宝石。请问，你最多可以收集到多少宝石。
这个游戏由$30001$个格子组成。 这些格子沿一条线均匀分布，从西到东编号为$0$到$30000$，每个格子的距离都是单位长度。
众所周知，格子游戏肯定要找宝藏。格子游戏一共藏有$n$颗宝石，第$i$颗宝石位于编号为$a_i$的格子上。
现在游戏的起点为$0$号格子，凭借着超强的跳跃能力，你会按照以下方式进行跳跃：
- 首先，你会从$0$号格子跳到$d$号格子。
- 第二步开始，你将按照以下规则继续跳跃： 令$l$为上一次跳跃的长度，那么这一次跳跃，你向前跳跃的长度只能是$l - 1$、$l$ 或 $l + 1$。限制：一次跳跃的长度必须为正，即当$l = 1$时，你不能进行长度为$0$的跳转。你随时可以自己决定结束游戏。
如果你到了一个有宝石的格子，你会收集这个格子上的宝石。请问，你最多可以收集到多少宝石。
输入格式
第一行有两个整数$n,d$，意义如题。
第二行有$n$个整数，分别是$a_1,a_2,\cdots,a_n$。
第二行有$n$个整数，分别是$a_1,a_2,\cdots,a_n$。
输出格式
输出一个整数，表示最多可以收集到的宝石数目。
输入输出样例
输入 #1
4 10 10 21 27 27
输出 #1
3
输入 #2
8 8 9 19 28 36 45 55 66 78
输出 #2
6
【样例解释】
样例1路线：0 -> 10(1个宝石) -> 19 -> 27(2个宝石)。
样例2路线：0 -> 8 -> 15 -> 21 -> 28(1个宝石) -> 36(1个宝石) -> 45(1个宝石) -> 55(1个宝石) -> 66(1个宝石) -> 78(1个宝石)。
【数据范围】
对于前$30\%$数据，$1 \leq d \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 15$；
对于前$70\%$的数据，$1 \leq d \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 5000$；
对于$100\%$的数据，$1\leq n \leq 30000$，$1\leq d \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 30000$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？