1 条题解

  • 0
    @ 2023-12-19 18:58:07
    #include <bits/stdc++.h>
    using namespace std;
    int n, a[110], f[110][110][110][2];
    bool vis[110][110][110][2];
    // 前p个数,第p个数,还剩c0个偶数,c1个奇数,取a[p]=x(x==0偶数,x==1奇数)
    int dfs(int p, int c0, int c1, int x) {
        if (a[p] && a[p]%2 != x) return -1;
        if (c0 < 0 || c1 < 0)
            return -1;
        if (!p)
            return 0;
        if (vis[p][c0][c1][x])
            return f[p][c0][c1][x];
        vis[p][c0][c1][x] = true;
        int &u = f[p][c0][c1][x];
        for (int i = 0; i < 2; i++) {
            int tmp = dfs(p-1, c0 - (x%2==0), c1 - (x%2==1), i);
            if (tmp == -1) continue;
            int d = (p > 1) && (i != x);
            if (u == -1 || u > tmp + d)
                u = tmp + d;
        }
        return u;
    }
    int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a+i);
        }
        memset(f, -1, sizeof f);
        int ans = -1;
        for (int i = 0; i < 2; i++) {
            int tmp = dfs(n, n/2, (n+1)/2, i);
            if (tmp != -1)
                if (ans == -1 || ans > tmp)
                    ans = tmp;
        }
        printf("%d\n", ans);
        return 0;
    }
    
    
    • 1

    信息

    ID
    13
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者