Garland

dp思路并不是那么明显,那么我们来思考下怎么贪心.
首先对于一种左右两边奇偶性相同的坑,无非就两种填法,一种是拿一种和它们颜色相同的全部填满,另外一种就是随便填填代价为2.
然后对于两边奇偶性不同的坑呢?无论你怎么填代价都为1吧?如此贪心的思路就很简单了.你先把那些等于偶数的坑和等于奇数的坑小的全部填了,然后剩下就是计算有几个坑了..注意边界.
代码如下:

//那种小点的模拟,用你的思维一步一步实现,不要急于整体实现..不然代码就会变得难写,尤其对于我这种菜鸡选手
#include <bits/stdc++.h>
using namespace std;
struct vv{
    int w,id;
};
const int N=105;
int a[N],cnt1[N],cnt2[N],id1,id2;//记录奇数坑,记录偶数坑.其他坑数量
vector<vv>v;
int main()
{
    int n,ans=0,odd_s,even_s;
    cin>>n;
    if(n&1) {odd_s=n/2+1; even_s=n/2;}
    else    {odd_s=n/2;   even_s=n/2;}
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]&1)
        {
            odd_s--;
            v.push_back({a[i],i});
        }
        else if(a[i]!=0)
        {
            even_s--;
            v.push_back({a[i],i});
        }
    }
    if(n==1)        {puts("0");return 0;}
    if(v.size()<=1) {puts("1");return 0;}
    for(int i=1;i<v.size();i++)
    {
        if(v[i].id-v[i-1].id==1)//两个是间隔的
        {
            if((v[i].w%2)!=(v[i-1].w%2)) ans++;
        }
        else//有坑
        {
            if((v[i].w%2)==(v[i-1].w%2))
            {
                if(v[i].w%2) { cnt1[id1++]=v[i].id-v[i-1].id-1; }
                else         { cnt2[id2++]=v[i].id-v[i-1].id-1; }
            }
            else ans++;
        }
    }int ed=v.size()-1;
    int obj1=0,ebj1=0,obj2=0,ebj2=0;
    if(v[0].id!=1)
    {
        if(v[0].w%2) { obj1=v[0].id-1; }
        else         { ebj1=v[0].id-1; }
    }
    if(v[ed].id!=n)
    {
        if(v[ed].w%2) { obj2=n-v[ed].id; }
        else          { ebj2=n-v[ed].id; }
    }
    sort(cnt1,cnt1+id1);
    sort(cnt2,cnt2+id2);
    for(int i=0;i<id1;i++)
    {
        if(odd_s-cnt1[i]>=0) odd_s-=cnt1[i];
        else                 ans+=2;
    }
    for(int i=0;i<id2;i++)
    {
        if(even_s-cnt2[i]>=0) even_s-=cnt2[i];
        else                  ans+=2;
    }
    if(obj1||obj2)
    {
        if(odd_s-obj1>=0) odd_s-=obj1;
        else              ans++;
        if(odd_s-obj2>=0) odd_s-=obj2;
        else              ans++;
    }
    if(ebj1||ebj2)
    {
        if(even_s-ebj1>=0) even_s-=ebj1;
        else              ans++;
        if(even_s-ebj2>=0) even_s-=ebj2;
        else              ans++;
    }
    cout<<ans<<endl;
    return 0;
}