fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. int n, k;
  6. cin>>n>>k;
  7. vector<int> arr(n+1, 0);
  8. for(int i=1;i<=n;i++){
  9. int element;
  10. cin>>element;
  11. arr[i]=element;
  12. }
  13. vector<int> dp(n+1,0);
  14. dp[1]=0;
  15. dp[2]=abs(arr[2]-arr[1]);
  16. for(int i=3;i<=n;i++){
  17. int answer=INT_MAX;
  18. for(int j=1;j<=k && i-j>=1;j++){
  19. //we are jumping from i-j to i
  20. int option=abs(arr[i]-arr[i-j]) + dp[i-j];
  21. answer=min(answer, option);
  22. }
  23. dp[i]=answer;
  24. }
  25. cout<<dp[n];
  26. return 0;
  27. }
  28.  
Success #stdin #stdout 0s 5320KB
stdin
10 4
40 10 20 70 80 10 20 70 80 60
stdout
40