Codeforces Round #612 (Div. 2) C. Garland

タイトル:https://codeforces.com/contest/1287/problem/C構想1:貪欲に全体の列を(0)段と非(0)段に分けるのは容易である:1つの(0)段の両端が偶数または奇数であれば、すべて偶数または奇数を記入し、そうでなければ(complexity+=2)1つの(0)段の両端のパリティが異なる場合、(complexity+=1)1つの(0)段が一端しかない場合、そのパリティと同じ数を記入する.そうでなければ(complexity+=1)両端を持つ(0)セグメントの長さを小さいものから大きいものに並べ替えて欲張りを行い、最後に一端のみを判断する(0)セグメント

#include
 
using namespace std;
 
const int N=105;
 
int n;
int a[N];
int b[2][N];
int t[2];
int c[3];
int ans;
pair st,ed;
 
void init()
{
    if((n&1)==0) c[0]=c[1]=n/2;
    else c[0]=n/2,c[1]=n/2+1;
}
void solve()
{
    int l=0,r=0,cnt=0;
    int pre=1;
    int f=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0)
        {
            if(cnt==0) l=pre&1;
            cnt++;
        }
        else
        {
            c[a[i]&1]--;
            if(a[i-1]!=0)
            {
                if((a[i]&1)!=(a[i-1]&1)) ans++;
            }
            if(cnt)
            {
                r=a[i]&1;
                if(!a[1]&&!f) f=1,st={cnt,r};
                else if(l==r) b[l][++t[l]]=cnt;
                else ans++;
                cnt=0;
            }
            pre=a[i];
        }
    }
    if(cnt) ed={cnt,l};
    sort(b[0]+1,b[0]+1+t[0]);
    sort(b[1]+1,b[1]+1+t[1]);
    for(int i=0;i<2;i++)
        for(int j=1;j<=t[i];j++)
        {
            if(c[i]>=b[i][j]) c[i]-=b[i][j];
            else ans+=2;
        }
    if(c[st.second]>=st.first) c[st.second]-=st.first;
    else ans++;
    if(c[ed.second]>n;
    init();
    for(int i=1;i<=n;i++) cin>>a[i];
    solve();
    return 0;
}

考え方2:dp 1次元:長さ、2次元:残りの偶数個数、3 D:現在数パリティ限界:偶数が存在し、最初の数が0または偶数である場合:(dp[1][n/2-1][0]=0)最初の数が(0)または奇数:(dp[1][n/2][1]=0)状態遷移:1現在の偶数:(dp[i][j-1][0]=min(dp[i][j-1][0]=min(dp[i][j-1][0],dp[k]+(k==1)))))②現在の奇数:(dp[i][j][1]=min(dp[i][j][1],dp[i-1][j][k]+(k==1))

#include
 
using namespace std;
 
const int N=105;
 
int n;
int a[N];
int dp[N][N][2];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("in.txt","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(dp,0x3f,sizeof dp);
    if(n>1&&(a[1]==0||a[1]%2==0)) dp[1][n/2-1][0]=0;
    if(a[1]==0||a[1]%2==1) dp[1][n/2][1]=0;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=n/2;j++)
            for(int k=0;k<2;k++)
            {
                if(j>0&&(a[i]==0||a[i]%2==0)) dp[i][j-1][0]=min(dp[i][j-1][0],dp[i-1][j][k]+(k==1));
                if(i+j-1