Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define loop(i,b,e) for(int i=b;i<=e;i++)
- #define loop2(i,e,b) for(int i=e;i>=b;i--)
- #define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
- #define fi first
- #define se second
- typedef long long ll;
- typedef unsigned long long ull;
- const int N = 1e6 + 5;
- const ll mod = 1e9 + 7;
- const int oo = 1e9;
- ll t[N];
- int n;
- int dp[N][3];
- int solve(int i,int last,ll prog) {
- if (i == n) return 0;
- ll curr;
- if (last == 0) curr = t[i-1];
- else if (last == 1) curr = t[i-1] + 1;
- else curr = t[i-1] - 1;
- int ret = oo;
- if (prog == -1) {
- ret = min(ret,solve(i + 1, 0, t[i] - curr));
- ret = min(ret, 1 + solve(i + 1, 1, t[i] - curr+1));
- ret = min(ret, 1 + solve(i + 1, 2, t[i] - curr-1));
- }
- else {
- if(t[i]-curr==prog) ret = min(ret, solve(i + 1, 0, t[i] - curr));
- if(t[i]-curr+1==prog) ret = min(ret, 1 + solve(i + 1, 1, t[i] - curr + 1));
- if(t[i]-curr-1==prog) ret = min(ret, 1 + solve(i + 1, 2, t[i] - curr - 1));
- }
- return ret;
- }
- int main() {
- scanf("%d",&n);
- memset(dp,-1,sizeof dp);
- loop(i, 0, n - 1)
- scanf("%lld",&t[i]);
- int ans = min(solve(1, 0, -1), min(1 + solve(1, 1, -1), 1 + solve(1, 2, -1)));
- cout << (ans==oo ? -1 : ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement