fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define REP(i,a,b) for(int i=a;i<b;i++)
  4. #define f first
  5. #define s second
  6. #define pb push_back
  7. #define mp make_pair
  8. #define endl "\n"
  9. #define mod 1000000007
  10. typedef long long ll;
  11. typedef vector<int> vi;
  12. typedef pair<int, int> pi;
  13. typedef unordered_map<int, int> umap;
  14. void inputarr(int arr[], int n) {REP(i, 0, n) {cin >> arr[i];}}
  15. int main() {
  16. ios_base::sync_with_stdio(0);
  17. cin.tie(0);
  18. int n,k;
  19. cin>>n>>k;
  20. int arr[n];
  21. inputarr(arr,n);
  22. vector<int>dp(n,0);
  23. dp[0]=0;
  24. dp[1]=abs(arr[1]-arr[0]);
  25. for(int i=2;i<n;i++){
  26. dp[i]=INT_MAX;
  27. for(int j=1;j<=k;j++){
  28. if(i-k>=0){
  29. dp[i] = min(dp[i-k] + abs(arr[i]-arr[i-k]),dp[i]);
  30. }
  31.  
  32. }
  33. // int c1 = abs(arr[i-1]-arr[i])+dp[i-1];
  34. // int c2 = abs(arr[i-2]-arr[i])+dp[i-2];
  35.  
  36. }
  37. cout<<dp[n-1];
  38.  
  39. }
Success #stdin #stdout 0.01s 5280KB
stdin
5 3
10 30 40 50 20
stdout
30