Advertisement
amine99

Untitled

May 13th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define loop(i,b,e) for(int i=b;i<=e;i++)
  4. #define loop2(i,e,b) for(int i=e;i>=b;i--)
  5. #define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  6. #define fi first
  7. #define se second
  8. typedef long long ll;
  9. typedef unsigned long long ull;
  10. const int N = 1e6 + 5;
  11. const ll mod = 1e9 + 7;
  12. const int oo = 1e9;
  13.  
  14. ll t[N];
  15. int n;
  16. int dp[N][3];
  17.  
  18. int solve(int i,int last,ll prog) {
  19.     if (i == n) return 0;
  20.     ll curr;
  21.     if (last == 0) curr = t[i-1];
  22.     else if (last == 1) curr = t[i-1] + 1;
  23.     else curr = t[i-1] - 1;
  24.     int ret = oo;
  25.     if (prog == -1) {
  26.         ret = min(ret,solve(i + 1, 0, t[i] - curr));
  27.         ret = min(ret, 1 + solve(i + 1, 1, t[i] - curr+1));
  28.         ret = min(ret, 1 + solve(i + 1, 2, t[i] - curr-1));
  29.     }
  30.     else {
  31.         if(t[i]-curr==prog) ret = min(ret, solve(i + 1, 0, t[i] - curr));
  32.         if(t[i]-curr+1==prog) ret = min(ret, 1 + solve(i + 1, 1, t[i] - curr + 1));
  33.         if(t[i]-curr-1==prog) ret = min(ret, 1 + solve(i + 1, 2, t[i] - curr - 1));
  34.     }
  35.     return ret;
  36. }
  37.  
  38. int main() {
  39.     scanf("%d",&n);
  40.     memset(dp,-1,sizeof dp);
  41.     loop(i, 0, n - 1)
  42.         scanf("%lld",&t[i]);
  43.     int ans = min(solve(1, 0, -1), min(1 + solve(1, 1, -1), 1 + solve(1, 2, -1)));
  44.     cout << (ans==oo ? -1 : ans);
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement