Josif_tepe

Untitled

Oct 15th, 2025
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <queue>
  4. #include <vector>
  5. #include <cstring>
  6. using namespace std;
  7. const int maxn = 1e5 + 10;
  8. const int INF = 2e9;
  9. int n, a[maxn];
  10. int k;
  11. int dp[maxn];
  12. int rec(int at) {
  13.     if(at == n - 1) {
  14.         return 0;
  15.     }
  16.     if(dp[at] != -1) {
  17.         return dp[at];
  18.     }
  19.    
  20.     int res = INF;
  21.    
  22.     for(int i = 1; i <= k; i++) {
  23.         if(at + i < n) {
  24.             int cost = abs(a[at] - a[at + i]);
  25.             res = min(res, rec(at + i) + cost);
  26.         }
  27.     }
  28.    
  29.     dp[at] = res;
  30.     return res;
  31. }
  32. int main() {
  33.     ios::sync_with_stdio(false);
  34.     memset(dp, -1, sizeof dp);
  35.    
  36.     cin >> n >> k;
  37.        
  38.     for(int i = 0; i < n; i++) {
  39.         cin >> a[i];
  40.     }
  41.    
  42.     cout << rec(0) << endl;
  43.     return 0;
  44. }
  45.  
Advertisement
Add Comment
Please, Sign In to add comment