C - Garland

#include <bits/stdc++.h>
using namespace std;

const int N = 111;
int n ,a[N] ,Memo[N][N][N][2];

int calc(int i ,int o ,int e ,int last){
    if( i < 0 ) return 0;

    int &re = Memo[i][o][e][last];
    if( re != -1  ) return re;
    if( a[i] != 0 ) return re = calc( i-1 ,o ,e ,a[i] % 2) + ( a[i] % 2 != last );

    int c1 = ( o > 0 ) ? calc(i-1 ,o-1 ,e ,1) + (last == 0) : INT_MAX;
    int c2 = ( e > 0 ) ? calc(i-1 ,o ,e-1 ,0) + (last == 1) : INT_MAX;
    return re = min( c1,c2 );
}

int main()
{
    cin >> n;
    int even = n / 2;
    int odd  = n - even;
    for(int i=0 ; i<n ; i++) {
        cin >> a[i];
        odd  -= ( a[i] % 2  );
        even -= ( a[i] % 2 == 0 && a[i] != 0 );
    }

    memset(Memo ,-1 ,sizeof Memo);
    int last = ( a[n - 1] != 0 ? a[n - 1] % 2 : 2 );
    cout << calc( n-1 ,odd ,even ,last) << endl;

    return 0;
}