fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.   int n, k;
  6.   cin >> n >> k;
  7.  
  8.   int a[n];
  9.   int dp[n];
  10.   for (int i = 0; i < n; i++) {
  11.     cin >> a[i];
  12.     dp[i] = INT_MAX;
  13.   }
  14.  
  15.  
  16.   dp[0] = 0;
  17.   for (int i = 1; i < n; i++) {
  18.     for (int j = i-1; j >= 0 && j >= i-k; j--) {
  19.       dp[i] = min(dp[i], dp[j]+abs(a[i]-a[j]));
  20.     }
  21.   }
  22.  
  23.   cout << dp[n-1] << "\n";
  24.   return 0;
  25. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 3
10 30 40 50 20
stdout
copy 
30
https://ideone.com/pFfJod
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!