fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int min_cost_to_make_jumpToN(vector<int> a, int k){
  5. int n = a.size();
  6.  
  7. vector<int> dp(n);
  8. dp[0] = 0;
  9. dp[1] = abs(a[1] - a[0]);
  10.  
  11. for (int i = 2; i < n; i++){
  12. int j = 1, ans = INT_MAX;
  13. while(j <= k && i-j >= 0){
  14.  
  15. ans = min(ans, abs(a[i]-a[i-j])+dp[i-j]);
  16. j++;
  17. }
  18. dp[i] = ans;
  19.  
  20. }
  21.  
  22. return dp[n-1];
  23. }
  24.  
  25. int main() {
  26.  
  27. int n, k; cin >> n >> k;
  28. // vector<int> a = {10, 20, 5000, 10};
  29. vector<int> a(n);
  30.  
  31. for(int &i : a){
  32. cin >> i;
  33. }
  34.  
  35. cout << min_cost_to_make_jumpToN(a, k);
  36.  
  37. return 0;
  38. }
Success #stdin #stdout 0.01s 5284KB
stdin
10 4
40 10 20 70 80 10 20 70 80 60
stdout
40