Advertisement
Josif_tepe

Untitled

Oct 24th, 2021
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. typedef long long ll;
  6. int main()
  7. {
  8.     int n;
  9.     cin >> n;
  10.     vector<int> v(n);
  11.     for(int i = 0; i < n; i++) {
  12.         cin >> v[i];
  13.     }
  14.    
  15.     vector<int> dp(n, 2e9);
  16.     dp[0] = 0;
  17.     for(int i = 0; i < n; i++) {
  18.         if(i + 1 < n) {
  19.             dp[i + 1] = min(dp[i + 1], dp[i] + abs(v[i] - v[i + 1]));
  20.         }
  21.         if(i + 2 < n) {
  22.             dp[i + 2] = min(dp[i + 2], dp[i] + abs(v[i] - v[i + 2]));
  23.         }
  24.     }
  25.     cout << dp[n - 1] << endl;
  26.  
  27.     return 0;
  28. }
  29. // frog(0) --> (frog(1), frog(2))
  30. // frog(1) --> frog(2), frog(3)
  31.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement