收藏题解
题目链接
以下代码是基于贪心：

#include <bits/stdc++.h>
using namespace std;
int a[110];
struct node
{
    int l,r,len;
};
vector<node>p;
bool cmp(node x,node y)
{
    return x.len<y.len;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        p.clear();
        memset(a,0,sizeof(a));
        int ans=0,cnt0=n/2,cnt1=n/2,t=0;
        if(n&1)
            cnt1++;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>0)
            {
                if(a[i-1]!=0&&a[i-1]%2!=a[i]%2)
                    ans++;
                if(a[i]&1)
                    cnt1--;
                else
                    cnt0--;
                if(i-t>1&&t>0)
                    p.push_back({t,i,i-t-1});
                t=i;
            }
        }
        if(cnt1+cnt0==n)//特判
        {
            if(n>1)
                printf("1\n");
            else
                printf("0\n");
            continue;
        }
        sort(p.begin(),p.end(),cmp);
        for(int i=0;i<p.size();i++)
        {
            node tmp=p[i];
            if((a[tmp.l]&1)==(a[tmp.r]&1))//奇偶性相同
            {
                if(a[tmp.l]&1)
                {
                    if(cnt1>=tmp.len)
                        cnt1-=tmp.len;
                    else
                        ans+=2;
                }
                else
                {
                    if(cnt0>=tmp.len)
                        cnt0-=tmp.len;
                    else
                        ans+=2;
                }
            }
            else//奇偶不同
                ans++;
        }
        //cout<<"ans="<<ans<<endl;
        int x=1;
        while(a[x]==0&&x<=n)
            x++;
        if(x>1&&x<=n)
        {
            if(a[x]&1)
            {
                if(cnt1>=x-1)
                    cnt1-=(x-1);
                else
                    ans++;
            }
            else
            {
                if(cnt0>=x-1)
                    cnt0-=(x-1);
                else
                    ans++;
            }
        }
        x=n;
        while(a[x]==0&&x>=1)
            x--;
        if(x<n&&x>=1)
        {
            if(a[x]&1)
            {
                if(cnt1>=n-x)
                    cnt1-=(n-x);
                else
                    ans++;
            }
            else
            {
                if(cnt0>=n-x)
                    cnt0-=(n-x);
                else
                    ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}