C.Garland

题意：一行上有一串灯泡，每个灯泡都有一个唯一的数字，从1~n，其中有些灯泡的编号未知，让我们放回灯泡的编号，使得这串灯泡的复杂度最低，复杂度最低的定义是：相邻两盏灯泡的编号尽量奇偶性相同，如果不同，则加一。

分析：我们采用DP做法，开四维空间f[i][j][k][2]，这里给出的数据范围非常小，\(1 <= n <= 100\)，三重循环的时间复杂度为\(1e6\)，是可以接受的，然后我们来解释这个状态定义，第一维是要填的数字下标，我们从左往右填，第二维是填了多少个偶数，第三维是填了多少个奇数，第4维是当前数的奇偶性，然后我们思考状态转移方程，我们可以分成两类，第一类是当前位置上有数，那我们判断当前数的奇偶性，然后可以从两个状态转移过来，如果上一位的状态和当前状态不一样，那么就+1花费，否则直接转移，对这两个状态取最优解，然后是当前位上没有填上数，那我们就需要更新两个状态，在这个位上填偶数和填奇数，同时我们还需要一些限制，统计当前位置前面0的个数，我们的第二维和第三维状态的个数要小于0的个数，不然无法转移。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 105;
int f[N][N][N][2];
int a[N];
int pre[N];
int odd, even;
int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        if (a[i] > 0)
        {
            if (a[i] % 2 == 0)
                ++even;
            else
                ++odd;
            pre[i] = pre[i - 1];
        }
        else
        {
            pre[i] = pre[i - 1] + 1;
        }
    }

    if (n % 2 == 0)
    {
        even = n / 2 - even;
        odd = n / 2 - odd;
    }
    else
    {
        even = n / 2 - even;
        odd = n / 2 + 1 - odd;
    }
    memset(f, 0x3f, sizeof f);
    //第二维和第三维为填充的偶数个数和奇数个数
    f[0][0][0][0] = 0;
    f[0][0][0][1] = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= even; ++j)
        {
            for (int k = 0; k <= odd; ++k)
            {
                if (a[i] > 0)
                {
                    if (j + k <= pre[i])
                    {
                        if (a[i] % 2 == 0)
                        {
                            f[i][j][k][0] = min(f[i - 1][j][k][0], f[i - 1][j][k][1] + 1);
                        }
                        else
                        {
                            f[i][j][k][1] = min(f[i - 1][j][k][0] + 1, f[i - 1][j][k][1]);
                        }
                    }
                }
                else
                {
                    if (j + k <= pre[i])
                    {
                        f[i][j][k][0] = min(f[i - 1][j - 1][k][0], f[i - 1][j - 1][k][1] + 1);
                        f[i][j][k][1] = min(f[i - 1][j][k - 1][0] + 1, f[i - 1][j][k - 1][1]);
                    }
                }
            }
        }
    }

    int res = 0x3f3f3f3f;
    res = min(f[n][even][odd][0], f[n][even][odd][1]);

    printf("%d\n", res);


    return 0;
}

C.Garland

原文：https://www.cnblogs.com/pixel-Teee/p/12171722.html