fork download
  1. #include <bits/stdc++.h>
  2. #define FOR(i,s,e) for (int i=s; i<=e; i++)
  3. #define FOD(i,s,e) for (int i=s; i>=e; i--)
  4. #define pb push_back
  5. #define INF INT_MAX
  6. #define SIZE 200000
  7.  
  8. using namespace std;
  9.  
  10. int N,K;
  11. int h[SIZE],dp[SIZE];
  12.  
  13. int main() {
  14. cin >> N >> K;
  15. dp[0]=0;
  16. FOR(i,1,N) {
  17. cin >> h[i];
  18. dp[i]=0;
  19. }
  20. dp[2]=abs(h[2]-h[1]);
  21. FOR(i,3,N) {
  22. dp[i]=INF;
  23. FOR(j,1,fmin(K,i-1)) {
  24. dp[i]=fmin(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
  25. }
  26. }
  27. cout << dp[N];
  28.  
  29. return 0;
  30. }
  31.  
Success #stdin #stdout 0s 4348KB
stdin
10 4
40 10 20 70 80 10 20 70 80 60
stdout
40