[普及-]93767题解

本题几乎与93766一模一样，因此只给出转移方程和代码，剩下可以查看93766题解理解

设 $dp_i$ 为跳到第 $i$ 石头时的最小花费。
可以轻易发现，本题的转移方程为：

$$dp_i = \min(dp_i , dp_{i - j} + \text{abs}(a[i] - a[i-j])) \text{其中} j \in [1,\min(m , i - m - 1)]$$

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
#define int long long
int dp[N] , a[N] , n;
signed main(){
    int m;
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		dp[i] = 0x3f3f3f3f;
	}
	dp[1] = 0;
	dp[2] = abs(a[1] - a[2]);
	for(int i = 3;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
            if(j == i) break;
			dp[i] = min(dp[i] , dp[i - j] + abs(a[i] - a[i - j]));
		}
	}
    cout << dp[n];
	return 0;
}