B4296 [蓝桥杯青少年组国赛 2022] 最少问题

• 题号：B4296
• 难度：普及−（2）
• 标签：搜索、贪心、2022、广度优先搜索 BFS、线性 DP、蓝桥杯青少年组
• 时间限制：1000 ms
• 内存限制：512 MB
• 样例数：1
• 提交 / 通过：8740 / 3706
• 抓取时间：2026-11-11T08:53:26.975Z
• 正文来源：problem.content（zh-CN）

题目描述

河面上有 $N$ 个木桩排成一排，每个木桩上都有一个数字，表示青蛙从当前木桩一次最多可跳跃的木桩个数（例如数字为 $2$，可以跳跃 $1$ 个或 $2$ 个木桩）。请计算青蛙从第 $1$ 个木桩跳跃到第 $N$ 个木桩所需的最少跳跃次数。

例如：$N=5$，木桩数字分别为 $2$、$1$、$5$、$1$、$3$ 时：

1. 第一次从第 $1$ 个木桩跳到第 $3$ 个木桩（跳跃 $2$ 个木桩）；
2. 第二次从第 $3$ 个木桩跳到第 $5$ 个木桩（跳跃 $2$ 个木桩）；

最少需要 $2$ 次跳跃。

输入格式

输入共两行：

• 第一行：一个正整数 $N$（$5 \leq N \leq 100$），表示木桩数量；
• 第二行：$N$ 个正整数（$1 \leq$ 正整数 $\leq 1000$），表示各木桩上的数字，数字间用空格隔开。

输出格式

输出一个整数，表示青蛙最少需要跳跃几次可到达最后一个木桩。

样例

样例 1 输入

5
2 1 5 1 3

样例 1 输出

2

由 fetch_luogu_statements.mjs v1.0.0 自动抓取生成；原始数据见 json/B4296.json。