Advertisement
Josif_tepe

Untitled

Nov 23rd, 2021
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int n;
  5. int niza[100005];
  6. int frog[100005];
  7.  
  8. int rec(int frog_at) {
  9.     if(frog_at == n - 1) {
  10.         return 0;
  11.     }
  12.     if(frog[frog_at] != -1) {
  13.         return frog[frog_at];
  14.     }
  15.     int result = 2e9;
  16.     if(frog_at + 1 < n) {
  17.        
  18.         result = min(result, rec(frog_at + 1) + abs(niza[frog_at] - niza[frog_at + 1]));
  19.     }
  20.     if(frog_at + 2 < n) {
  21.         result = min(result, rec(frog_at + 2) + abs(niza[frog_at] - niza[frog_at +
  22.                                                                          2]));
  23.     }
  24.     return frog[frog_at] = result;
  25. }
  26. int main()
  27. {
  28.     cin >> n;
  29.     for(int i = 0; i < n; i++) {
  30.         cin >> niza[i];
  31.     }
  32.     for(int i = 0; i <= n; i++) {
  33.         frog[i] = -1;
  34.     }
  35.     cout<< rec(0) << endl;
  36.     return 0;
  37. }
  38. /*
  39.  rec(0) = MIN(rec(1) + 20 || rec(2) + 30) = MIN(30, 50) = 30
  40.  rec(1) = MIN(rec(2) + 10 || rec(3) + 10) = Min(30, 10) = 10
  41.  rec(2) = MIN(rec(3) + 20) = 20
  42.  rec(3)  = 0
  43.  **/
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement