CF-1287C Garland 题解

题目大意

给你一个数列，数列中每一个数不能重复，大小为1~n，0则表示该位置为空，需要填上数字。问你如何填满数列，使相邻两个数奇偶性不同的个数最小。求这个最小值。

解题思路

这个题目有两个方法，一个是DP，一个是贪心。

贪心代码太麻烦了，就不用贪心了。

我们可以用dp[i] [j] [flag]表示，前i位中有j个偶数并且当前为奇数或偶数的最优解，即最小的个数。当flag为0时，为偶数，flag为1时，为奇数。

（三维DP。。第一次写这种题。。完全没有思路，看的别人大佬的代码。。

这样就可以得出状态转移方程

当该位为奇数或者为0时

dp[i] [j] [1] = min(dp[i] [j] [1],dp[i-1] [j] [1]);（前一个数为奇数时）

dp[i] [j] [1] = min(dp[i] [j] [1],dp[i-1] [j] [0]+1);（前一个数为偶数时）

当该位为偶数或者为0时

dp[i] [j+1] [0] = min(dp[i] [j+1] [0],dp[i-1] [j] [0]);（前一个数为偶数时）

dp[i] [j+1] [0] = min(dp[i] [j+1] [0],dp[i-1] [j] [1]+1);（前一个数为奇数时）

（太难想了吧。。根本想不到

答案为min(dp[n] [n/2] [1],dp[n] [n/2] [0])。

完整代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int num[110];
int dp[110][110][2];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> num[i];
	memset(dp, 127, sizeof(dp));
    //补充知识
    //一般用memset只赋值0，1，-1，127
    //127表示填充最大值，即INF
	dp[0][0][0] = dp[0][0][1] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n / 2 ; j++) {
			if (num[i] % 2 == 0 || !num[i]) {
				dp[i][j + 1][0] = min(dp[i][j + 1][0], dp[i - 1][j][0]);//前一个数为偶数时
				dp[i][j + 1][0] = min(dp[i][j + 1][0], dp[i - 1][j][1] + 1);//前一个数为奇数时
			}
			if (num[i] % 2 == 1 || !num[i]) {
				dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1]);//前一个数为奇数时
				dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][0] + 1);//前一个数为偶数时
			}
		}
	}
	cout << min(dp[n][n / 2][1], dp[n][n / 2][0]) << endl;
}