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

LPR_318 · 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;
}