josiftepe

Untitled

Nov 14th, 2020
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5. const int INF = 2e9 + 5;
  6. int n;
  7. int a[100000];
  8. int dp[100000];
  9.  
  10. int rec(int at) /*at znaci na koja pozicija vo nizata se naogjam momentalno*/ {
  11.     if(at == n - 1) {
  12.         return 0; /*ako sme na kraj ne treba da skokame pak i vrakame 0*/
  13.     }
  14.     if(dp[at] != -1) {
  15.         return dp[at];
  16.     }
  17.     int ret = INF;
  18.     if(at + 1 < n) {
  19.         int cost = abs(a[at] - a[at + 1]);
  20.         ret = min(ret, rec(at + 1) + cost);
  21.     }
  22.     if(at + 2 < n) {
  23.         int cost = abs(a[at] - a[at + 2]) /*abs - absolutna vrednost*/;
  24.         ret = min(ret, rec(at + 2) + cost);
  25.     }
  26.     dp[at] = ret;
  27.     return ret;
  28. }
  29.  
  30. int main(){
  31.     cin>>n;
  32.     for (int i=0;i<n;i++){
  33.         cin>>a[i];
  34.         dp[i]=-1;
  35.     }
  36.     cout<<rec(0);
  37.     return 0;
  38. }
  39.  
Advertisement
Add Comment
Please, Sign In to add comment