A93767 正经题解

题意分析
这是一道经典的水题线性动态规划问题，是 $A93766$ 的拓展，每次可以选择走 $s$ 步（$1\leq s\leq k$），求到终点的最小代价。
解题思路
我们先要知道，动态规划的根本——子问题是什么，即 $dp_i$ 应该表示什么。
要跳到任何一块石阶上，青蛙只有 $k$ 种跳法，从前 $k$ 块石阶跳过来。因此我们可以发现，跳到这一块石阶的最小花费，即 $dp_i$，是由前 $k$ 块台阶转移而来的。青蛙不用动就已经在第一块石阶上，因此 $dp_1$ 为 $0$。青蛙只能从第一块石阶跳到第二块石阶上，因此 $dp_2$ 为第一、二块石阶的高度差。接下来，根据这些信息就可以得知第三块、第四块、第五块……
AC代码

#include <bits/stdc++.h>
using namespace std;
long long h[100005], dp[100005];

int main(){
    int n, k;
    cin >> n >> k;
    for(int i=1;i<=n;++i){
        cin >> h[i];
        dp[i] = 1e9+7;
    }
    dp[1] = 0;
    for(int i=2;i<=n;++i){
        for(int j=1;j<=k;++j){
            if(i-j>0) dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[i]);
        }
    }
    cout << dp[n];
    
    return 0;
}

时间复杂度
$O(n\times k)$，可以接受。