[CF1286A] Garland

Description

有一个由 $ 1 $ - $ n $ 构成的排列，其中部分被删除（删除的元素由 $ 0 $ 代替），请用被删除的元素补全这个数列，使这个数列中相邻元素奇偶性不同的对数最少。(n le 100)

Solution

设 (f[i][j][0/1]) 表示用了 (i) 个奇数，(j) 个偶数，上一位是奇数或偶数时的最小值

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 105;

int f[N][N][2],a[N],n;

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(f,0x3f,sizeof f);
    f[0][0][0]=f[0][0][1]=0;
    for(int l=1;l<=n;l++) {
        for(int i=0;i<=l;i++) {
            int j=l-i;
            if(a[l]) {
                if(a[l]&1) {
                    if(i>0) f[i][j][1]=min(f[i-1][j][0]+1,f[i-1][j][1]);
                }
                else {
                    if(j>0) f[i][j][0]=min(f[i][j-1][0],f[i][j-1][1]+1);
                }
            }
            else {
                if(i>0) f[i][j][1]=min(f[i-1][j][1],f[i-1][j][0]+1);
                if(j>0) f[i][j][0]=min(f[i][j-1][0],f[i][j-1][1]+1);
            }
        }
    }
    /*for(int i=0;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            cout<<f[i][j][0]<<"|"<<f[i][j][1]<<" ";
        }
        cout<<endl;
    }*/
    cout<<min(f[(n+1)/2][n/2][0],f[(n+1)/2][n/2][1]);
}