题目链接：https://codeforces.com/contest/1287/problem/C
题目大意：有一个序列是1-n的置换。有若干个数被拿走。用0表示，现在让你把这几个数放回去。如果相邻的两个数奇偶性不同，那么贡献+1.现在让你放回去要求贡献最小。

思路：直接dp:
dp[i][j][k][0/1]： 前i个数剩余j个奇数k个偶数，当前数为偶/奇时的最小贡献。

因为j+k恒定，可以降维。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
 
int a[105];
int f[105][55][55][2];
int main()
{
    int n, s1=0, s2=0, s3=0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        s3+=a[i];
        if(a[i]%2==1){
            s1++;
        }
        else if(a[i]!=0){
            s2++;
        }
    }
    memset(f, -1, sizeof(f));
 
    s1=n/2-s1+(n%2==1?1:0);
    s2=n/2-s2;
    if(a[1]==0){
        if(s1>0){
            f[1][s1-1][s2][1]=0;
        }
        if(s2>0){
            f[1][s1][s2-1][0]=0;
        }
    }
    else{
        f[1][s1][s2][a[1]%2]=0;
    }
    for(int i=2; i<=n; i++){
        if(a[i]==0){
            for(int j=0; j<=50; j++){
                for(int k=0; k<=50; k++){
                    if(f[i-1][j][k][0]!=-1){
                        if(j>0){
                            if(f[i][j-1][k][1]==-1){
                                f[i][j-1][k][1]=f[i-1][j][k][0]+ 1;
                            }
                            else{
                                f[i][j-1][k][1]=min(f[i-1][j][k][0]+ 1, f[i][j-1][k][1]);
                            }
 
                        }
                        if(k>0){
                            if(f[i][j][k-1][0]==-1){
                                f[i][j][k-1][0]=f[i-1][j][k][0];
                            }
                            else{
                                f[i][j][k-1][0]=min(f[i-1][j][k][0], f[i][j][k-1][0]);
                            }
 
                        }
                    }
                    if(f[i-1][j][k][1]!=-1){
 
                        if(j>0){
                            if(f[i][j-1][k][1]==-1)
                            f[i][j-1][k][1]=f[i-1][j][k][1];
                            else{
                                f[i][j-1][k][1]=min(f[i-1][j][k][1], f[i][j-1][k][1]);
                            }
                        }
                        if(k>0){
                            if(f[i][j][k-1][0]==-1)
                            f[i][j][k-1][0]=f[i-1][j][k][1]+ 1;
                            else{
                                f[i][j][k-1][0]=min(f[i-1][j][k][1]+ 1, f[i][j][k-1][0]);
                            }
                        }
                    }
                }
            }
        }
        else{
            for(int j=0; j<=50; j++){
                for(int k=0; k<=50; k++){
                    if(f[i-1][j][k][0]!=-1){
                        if(f[i][j][k][a[i]%2]==-1)
                        f[i][j][k][a[i]%2]=f[i-1][j][k][0]+((a[i]%2==1)?1:0);
                        else{
                            f[i][j][k][a[i]%2]=min(f[i-1][j][k][0]+((a[i]%2==1)?1:0), f[i][j][k][a[i]%2]);
                        }
                    }
                    if(f[i-1][j][k][1]!=-1){
                        if(f[i][j][k][a[i]%2]==-1)
                        f[i][j][k][a[i]%2]=f[i-1][j][k][1]+((a[i]%2==1)?0:1);
                        else{
                            f[i][j][k][a[i]%2]=min(f[i-1][j][k][1]+((a[i]%2==1)?0:1), f[i][j][k][a[i]%2]);
                        }
                    }
                }
            }
        }
    }
    if(f[n][0][0][0]==-1){
        printf("%d\n", f[n][0][0][1]);
    }
    else if(f[n][0][0][1]==-1){
        printf("%d\n", f[n][0][0][0]);
    }
    else{
        printf("%d\n", min(f[n][0][0][1], f[n][0][0][0]));
    }
 
    return 0;
}