题解 CF1286A 【Garland】

· · 题解

CF1286A题解

整理博客的时候改了一下分类标签，重新审核一下
dp
觉得这题作为一个C比div2的B要简单点吧，算是找回点dp的信心。。。
首先可以想到，只需关心每个数的奇偶，具体是几不用记录
所以0表示偶数，1表示奇数，-1表示不确定，存在a[]中

### 状态： $f[i][o][j][0/1]$: 考虑前$i$位，还剩$o$个偶数能用，剩$j$个奇数能用，第$i$位填的是偶数/奇数 ### 初始： 先都设为极大值 - 第一位填好了：$f[1][num[0]][num[1]][a[1]]=0

转移：

答案：

当然是\min(f[n][0][0][1],f[n][0][0][0])

 
其实代码中好多取\min是不需要的，但是为了方便就都写上了懒得想
另外状态可能还能再优化？欢迎评论区指出
 

code.$,复杂度$O(n^3) 
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define R register
#define EN printf("\n")
#define LL long long
inline int read(){
    int x=0,y=1;
    char c=std::getchar();
    while(c<'0'||c>'9'){if(c=='-') y=-1;c=std::getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
    return x*y;
}
int n;
int f[106][106][106][2];
int a[106],num[2];
inline void min(int &x,int y){(x>y)&&(x=y);}
int main(){
    n=read();
    for(R int i=1;i<=n;i++){
        a[i]=read();
        if(!a[i]){a[i]=-1;continue;}
        a[i]&=1;
        num[a[i]]++;
    }
    num[1]=(n&1?n/2+1:n/2)-num[1];num[0]=n/2-num[0];
    std::memset(f,0x3f,sizeof f);
    if(a[1]==-1){
        if(num[0]>0) f[1][num[0]-1][num[1]][0]=0;
        if(num[1]>0) f[1][num[0]][num[1]-1][1]=0;
    }
    else if(a[1]) f[1][num[0]][num[1]][1]=0;
    else f[1][num[0]][num[1]][0]=0;
    for(R int i=2;i<=n;i++){
        if(a[i]!=-1){
            for(R int o=num[0];o>=0;o--){
                for(R int j=num[1];j>=0;j--)
                    min(f[i][o][j][a[i]],f[i-1][o][j][1]+(a[i]!=1)),
                    min(f[i][o][j][a[i]],f[i-1][o][j][0]+(a[i]!=0));
            }
            continue;
        }
        for(R int o=num[0];o>=0;o--){
            for(R int j=num[1];j>=0;j--){
                min(f[i][o][j][1],f[i-1][o][j+1][1]);
                min(f[i][o][j][1],f[i-1][o][j+1][0]+1);
                min(f[i][o][j][0],f[i-1][o+1][j][0]);
                min(f[i][o][j][0],f[i-1][o+1][j][1]+1);
            }
        }
    }
    std::printf("%d",std::min(f[n][0][0][1],f[n][0][0][0]));
    return 0;
}