自动搬运

查看原文

来自洛谷，原作者为

	yuruilin2026 「形骸的残响に绊され灭びゆく都市を」|| INFP-T

搬运于2025-08-24 21:18:26，当前版本为作者最后更新于2025-04-07 17:10:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一些闲话：

膜拜神犇 Hootime。
一道很好的贪心题，同时也是一道很好的搜索题。
可惜我用 DP。

思路：

令 $dp_i$ 表示走到第 $i$ 个木桩的最小跳跃次数。
令 $a_i$ 表示第 $i$ 个木桩能跳的距离。
对于每一个 $i(i \ge 2)$，枚举一个小于 $i$ 的 $j$，若 $j+a_j \ge i$，则 $dp_i$ 就可以从 $dp_j$ 转移。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define min(a,b) (a<b?a:b)
int n,a[1005],dp[1005];
signed main(){
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i) cin >> a[i];
    for(int i = 2;i <= n;++i){
    	dp[i] = INT_MAX;
		for(int j = 1;j < i;++j){
			if(j + a[j] >= i) dp[i] = min(dp[i],dp[j] + 1);
		}
	}
	cout << dp[n];
    return 0;
}