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
", res);


	return 0;
}