Josif_tepe

Untitled

Oct 15th, 2025
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 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.  
  11. int dp[maxn];
  12. int rec(int at) {
  13.     if(at == n - 1) {
  14.         return 0;
  15.     }
  16.    
  17.     if(dp[at] != -1) {
  18.         return dp[at];
  19.     }
  20.    
  21.     int res = INF;
  22.    
  23.     if(at + 1 < n) {
  24.         int cost = abs(a[at] - a[at + 1]);
  25.         int res1 = rec(at + 1) + cost;
  26.         res = min(res, res1);
  27.     }
  28.    
  29.     if(at + 2 < n) {
  30.         int cost = abs(a[at] - a[at + 2]);
  31.         int res2 = rec(at + 2) + cost;
  32.         res = min(res, res2);
  33.     }
  34.    
  35.     dp[at] = res;
  36.     return res;
  37. }
  38. int main() {
  39.     ios::sync_with_stdio(false);
  40.     memset(dp, -1, sizeof dp);
  41.    
  42.     cin >> n;
  43.    
  44.     for(int i = 0; i < n; i++) {
  45.         cin >> a[i];
  46.     }
  47.    
  48.     cout << rec(0) << endl;
  49.     return 0;
  50. }
  51.  
Advertisement
Add Comment
Please, Sign In to add comment