Advertisement
Guest User

D

a guest
Apr 7th, 2019
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long lint;
  4. typedef long double llf;
  5. typedef pair<int, int> pi;
  6. typedef vector<int> vi;
  7.  
  8. int n, a[1000005];
  9.  
  10. int dp[1000005][3];
  11. int cst[3][3][3];
  12.  
  13. int cost(int s, int e, int x){
  14.     return cst[s+1][e+1][x+1];
  15. }
  16.  
  17. int f(int x, int d){
  18.     if(x == n) return 0;
  19.     if(~dp[x][d]) return dp[x][d];
  20.     int ret = 1e9;
  21.     for(int j=d; j<3; j++){
  22.         ret = min(ret, f(x+1, j) + cst[d][j][a[x+1]+1]);
  23.     }
  24.     return dp[x][d] = ret;
  25. }
  26.  
  27. int main(){
  28.     scanf("%d",&n);
  29.     assert(n >= 2 && n <= 1000000);
  30.     for(int i=1; i<=n; i++){
  31.         scanf("%d",&a[i]);
  32.     }
  33.     for(int i=-1; i<=1; i++){
  34.         for(int j=-1; j<=1; j++){
  35.             for(int k=-1; k<=1; k++){
  36.                 int l = 0;
  37.                 while(l <= 5){
  38.                     if(k + i * l == j) break;
  39.                     l++;
  40.                 }
  41.                 cst[i+1][j+1][k+1] = (l > 5 ? 987654321 : l);
  42.             }
  43.         }
  44.     }
  45.     memset(dp, -1, sizeof(dp));
  46.     int prnt = f(1, a[1] + 1);
  47.     if(prnt > 1e8) puts("Mumkun emes");
  48.     else printf("%d\n", prnt);
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement