Josif_tepe

Untitled

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