CF1286A

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;

int n;
int cnt[2];
int a[1 << 7], zc[1 << 7];

int dp[1 << 7][1 << 7][2]; // dp[i][j][0/1] means in i-th place, using j th odd number, ending in even/odd number
                           // the min score we can get

int main(int argc, char **argv)
{
    int max_v = 0x3F3F3F3F;
    memset(dp, 0x3F, sizeof(dp));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        if (a[i])
            cnt[a[i] % 2]++, zc[i] = zc[i - 1];
        else
            zc[i] = zc[i - 1] + 1;
    }
    int ocap = (n + 1) / 2 - cnt[1];
    int ecap = n / 2 - cnt[0];

    if (a[1] == 0) {
        dp[1][0][1] = max_v;
        dp[1][1][1] = 0;
        dp[1][0][0] = 0;
        dp[1][1][0] = max_v;
    } else {
        int f = a[1] % 2;
        dp[1][0][f] = 0;
        dp[1][1][f] = max_v;
        dp[1][0][f ^ 1] = max_v;
        dp[1][1][f ^ 1] = max_v;
    }

    for (int i = 2; i <= n; ++i) {
        int f = a[i] % 2;
        if (a[i]) {
            for (int j = 0; j <= ocap; ++j) {
                dp[i][j][f] = min(dp[i - 1][j][0] + (f == 0 ? 0 : 1), dp[i - 1][j][1] + (f == 1 ? 0 : 1));
                dp[i][j][f ^ 1] = max_v;
            }
        } else {
            for (int j = 0; j <= zc[i] && j <= ocap; ++j) {
                dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + 1);
            }
            for (int j = 1; j <= zc[i] && j <= ocap; ++j) {
                dp[i][j][1] = min(dp[i - 1][j - 1][0] + 1, dp[i - 1][j - 1][1]);
            }
        }
    }
    printf("%d\n", min({dp[n][ocap][0], dp[n][ocap][1]}));
    return 0;
};