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