Atcoder Educational Dp contest :: B frog 2
#include <bits/stdc++.h> using namespace std ; #define ll long long const int inf = 1e9 + 5 ; const int mod = 1e9 + 7 ; int main (){ ll n , k ; cin >> n >> k ; vector < ll > a(n) ; for ( ll i= 0 ; i<n ; i++)cin >> a [ i ] ; vector < ll > dp(n , inf) ; dp [ 0 ] = 0 ; for ( ll i= 0 ; i<n ; i++){ for ( ll j=i+ 1 ; j<=i+k ; j++){ if (j<n){ dp [ j ] = min(dp [ j ] , dp [ i ] +abs(a [ i ] - a [ j ] )) ; } } //cout<<dp[i]<<" "; } cout << dp [ n- 1 ] ; }