Garland

= - =又是一个新东西,不合法的可以直接转移...dp还是简单

#include <bits/stdc++.h>
using namespace std;
const int N=105;
int a[N];
int f[N][N][2];//到了第i个没填j个偶数数这个点填奇数/偶数
int main()
{
    int n,ans=0;
    cin>>n;
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    if(a[1]==0||a[1]%2==1)  f[1][n/2][0]=0;//填奇数
    if(a[1]==0||a[1]%2==0)  f[1][n/2-1][1]=0;//填偶数
    for(int i=2;i<=n;i++)//到了i的位子
    {
        for(int j=0;j<=n/2;j++)//还有j个偶数没分配
        {
            if(a[i]==0||a[i]%2==1)//填奇数
            {
                f[i][j][0]=min(f[i][j][0],min(f[i-1][j][1]+1,f[i-1][j][0]));
            }
            if(a[i]==0||a[i]%2==0)//填偶数
            {
                f[i][j-1][1]=min(f[i][j-1][1],min(f[i-1][j][1],f[i-1][j][0]+1));
            }
        }
    }
    cout<<min(f[n][0][1],f[n][0][0])<<endl;
    return 0;
}