Advertisement
Guest User

D

a guest
Apr 7th, 2019
252
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <set>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. const int N = 1000000;
  11. const int oo = N + 1;
  12.  
  13. int n;
  14. int a[N];
  15. int d[N][3];
  16.  
  17.  
  18. int main() {
  19.   cin >> n;
  20.   assert(1 <= n && n <= N);
  21.   for (int i = 0; i < n; i++) {
  22.     cin >> a[i];
  23.     assert(a[i] == -1 || a[i] == 0 || a[i] == 1);
  24.     a[i] += 1;
  25.   }
  26.   for (int i = 0; i < n; i++) {
  27.     for (int j = 0; j < 3; j++) {
  28.       d[i][j] = oo;
  29.     }
  30.   }
  31.  
  32.   d[0][a[0]] = 0;
  33.  
  34.   for (int i = 1; i < n; i++) {
  35.     for (int j = 0; j < 3; j++) if (j <= a[i]) {
  36.       d[i][a[i]] = min(d[i][a[i]], d[i-1][j]);
  37.     }
  38.     for (int j = 0; j < 3; j++) {
  39.       for (int c = 1; c <= 2; c++) {
  40.         int k = c * (j - 1) + a[i];
  41.         if (k >= 0 && k < 3 && j <= k) {
  42.           d[i][k] = min(d[i][k], d[i-1][j] + c);
  43.         }
  44.       }
  45.     }
  46.   }
  47.  
  48.   int r = oo;
  49.   for (int j = 0; j < 3; j++) {
  50.     r = min(r, d[n - 1][j]);
  51.   }
  52.   if (r == oo) {
  53.     cout << "Mumkun emes" << endl;
  54.   } else {
  55.     cout << r << endl;
  56.   }
  57.   return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement