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