A34377. 最少问题
填空题
困难
知识点
题目描述
最少问题
题目描述
河面上有N个木桩排成一排，且每个木桩上都有一个数字，木桩上的数字表示青蛙从当前木桩一次最多可跳跃的木桩个数（例如木桩上的数字为2，青蛙可以跳跃一个木桩也可以跳跃两个木桩）。请你帮助青蛙计算出从第一个木桩跳跃到最后一个木桩最少需要跳跃几次。
例如：N=5，5个木桩上的数字分别为2，1，5，1，3。
第一次跳跃，青蛙从第一个木桩跳跃到第三个木桩，共跳了2个木桩；
第二次跳跃，青蛙从第三个木桩跳跃到最后一个木桩，共跳了2个木桩；
故最少需要跳跃2次可到达最后一个木桩 。
输入描述
第一行输入一个正整数N（5≤N≤100），N表示河面上的木桩个数
第二行输入N个正整数（1≤正整数≤1000），表示每个木桩上的数字，正整数之间以一个空格隔开（输入的正整数顺序为木桩的排列顺序，第一个正整数为第一个木桩上的数字）
输出描述
输出一个整数，表示青蛙最少需要跳跃几次可到达最后一个木桩
样例输入
5
2 1 5 1 3
样例输出
2
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 107;
int n, a[N], dp[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
dp[i] = 99;
dp[0] = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j <= i+a[i]; j++)
if (j < n)
dp[j] = min(dp[j], dp[i] + 1);
printf("%d\n", dp[n-1]);
return 0;
}
上一题
下一题