徐老师的弹簧板改良
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
大家都做过一个基础的递推题——《弹簧板》在一个长度为 $n$ 的坐标轴上，每个坐标点 $(1 \sim n)$ 都有一个弹簧板，第 $i$ 个弹簧力度为 $b_i$，当触发它的时候会将人弹到 $i + b_i$ 处
现在徐老师想修改一下这道题里的弹簧板，让弹簧板不但可以向后，还能向前！
修改后的弹簧板除了原本的属性 $b_i$ 表示向右弹的力度外，会获得另一个属性 $a_i$ 表示向左弹的力度
而因为向左弹的功能是徐老师加的，所以徐老师可以通过自身姿势/力量的调整使得他站在 $i$ 上时，可以跳到任意的位置 $j(i - a_i \leq j \leq i)$
但是当徐老师通过弹簧板向左跳到某个位置 $j$ 后，他会被动的触发一次第 $j$ 个弹簧向右弹的效果，即被弹到 $j + b_j$
现在徐老师想知道，他从 $n$ 出发最少跳几次可以回到坐标 $0$ 处？（这里我们认为坐标 $0$ 处没有弹簧板）
输入格式
输入第一行包含一个整数 $n$ 表示坐标轴长度输入第二行包含 $n$ 个整数 $a_i$ 分别表示第 $i$ 个弹簧向左弹的力度
输入第三行包含 $n$ 个整数 $b_i$ 分别表示第 $i$ 个弹簧向右弹的力度
|测试点|$n$|
|:---:|:---:|
|$1 \sim 3$|$1 \leq n \leq 500$|
|$4 \sim 5$|$1 \leq n \leq 3000$|
|$6 \sim 10$|$1 \leq n \leq 3 * 10^5$|
对于所有数据保证：$0 \leq a_i \leq i, 0 \leq b_i \leq n-i$
输出格式
输出徐老师最少需要跳的次数，若无法回到 $0$ 点则输出 $-1$样例
10
0 1 2 3 5 5 6 7 8 5
9 8 7 1 5 4 3 2 0 03提示
跳跃路径为：1. 从 $10$ 跳到 $9$ 被弹到 $9+0=9$
2. 从 $9$ 跳到 $4$ 被弹到 $4+1=5$
3. 从 $5$ 跳到 $0$ 结束
23CSP-J秋季普及组模拟赛(10)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2023-10-14 12:00
- 结束于
- 2023-10-24 12:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 41
