Advertisement
ismaeil

C - Garland

Apr 28th, 2020
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 111;
  5. int n ,a[N] ,Memo[N][N][N][2];
  6.  
  7. int calc(int i ,int o ,int e ,int last){
  8.     if( i < 0 ) return 0;
  9.  
  10.     int &re = Memo[i][o][e][last];
  11.     if( re != -1  ) return re;
  12.     if( a[i] != 0 ) return re = calc( i-1 ,o ,e ,a[i] % 2) + ( a[i] % 2 != last );
  13.  
  14.     int c1 = ( o > 0 ) ? calc(i-1 ,o-1 ,e ,1) + (last == 0) : INT_MAX;
  15.     int c2 = ( e > 0 ) ? calc(i-1 ,o ,e-1 ,0) + (last == 1) : INT_MAX;
  16.     return re = min( c1,c2 );
  17. }
  18.  
  19. int main()
  20. {
  21.     cin >> n;
  22.     int even = n / 2;
  23.     int odd  = n - even;
  24.     for(int i=0 ; i<n ; i++) {
  25.         cin >> a[i];
  26.         odd  -= ( a[i] % 2  );
  27.         even -= ( a[i] % 2 == 0 && a[i] != 0 );
  28.     }
  29.  
  30.     memset(Memo ,-1 ,sizeof Memo);
  31.     int last = ( a[n - 1] != 0 ? a[n - 1] % 2 : 2 );
  32.     cout << calc( n-1 ,odd ,even ,last) << endl;
  33.  
  34.     return 0;
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement