Advertisement
Josif_tepe

Untitled

Oct 24th, 2021
146
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 <vector>
  3. #include <queue>
  4. using namespace std;
  5. typedef long long ll;
  6. int n;
  7. int h[100005];
  8. int dp[100005];
  9. int frog(int i) {
  10.     if(i == n - 1) {
  11.         return 0;
  12.     }
  13.     if(dp[i] != -1) {
  14.         return dp[i];
  15.     }
  16.     int result = 2e9;
  17.     if(i + 1 < n) {
  18.         result = min(result, frog(i + 1) + abs(h[i] - h[i + 1]));
  19.     }
  20.     if(i + 2 < n) {
  21.         result = min(result, frog(i + 2) + abs(h[i] - h[i + 2]));
  22.     }
  23.     dp[i] = result;
  24.     return result;
  25. }
  26. int main()
  27. {
  28.     cin >> n;
  29.     for(int i = 0; i < n; i++) {
  30.         cin >> h[i];
  31.         dp[i] = -1;
  32.     }
  33.     cout << frog(0) << endl;
  34.  
  35.     return 0;
  36. }
  37. // frog(0) --> (frog(1), frog(2))
  38. // frog(1) --> frog(2), frog(3)
  39.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement