B. Garland - 1800
原题链接
Codeforces Round 612 (Div. 1) A
Codeforces Round 612 (Div. 2) C
题目大意
给定一个被删去字符的 \(1\sim n\) 排列，现在需要将空缺位置填入缺失的数，使得最终得到的序列仍是一个 \(1\sim n\) 的排列，问所有填法中，相邻两项的奇偶性不同的数对数量最小值是多少。
解题思路
注意到本题数据范围只到 \(100\)，所以dp到 \(O(n^3)\) 也是可以通过的。
我们开一个四维dp数组dp[i][j][k][ok]，其中最后一维仅包含01，表示我们当前位置的奇偶性，这个数组表示前 \(i\) 位元素替换 \(j\) 个偶数，\(k\) 个奇数后，当前元素奇偶性为 \(ok\) 的最小奇偶交换次数（这里的奇偶交换次数指的就是题目所说的数对数量，从头遍历到尾部发生奇偶交换就表明存在一个这样的数对）。
确定完我们的状态表示之后需要确定我们的转移方程。
注意到如果我们遍历到的位置是一个既定元素，那么这个位置的dp值是固定的，但是由于不知道给定的数组是什么样的，所以这里依旧需要对奇偶性不同的情况取最小值。反之如果遍历到的是一个空元素，那么我们需要对这个填入元素的奇偶性做出讨论，与前一个相比发生奇偶改变则对dp值加一。
最后我们的答案是对两种结尾奇偶性取小者，前三维一定是 dp[n][remain(even)][remain(odd)]，也就是数组前 \(n\) 个元素，恰好用掉可用的所有偶数和奇数的情况下，最小奇偶交换次数。
因为我们不需要考虑具体值，只需要在意奇偶性，所以题目所说的 \(1\sim n\) 的排列是一定可以得到满足的，可以忽略这个限制。
AC Code
#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;
const int N = 110;
const int MOD = 1e9 + 7;
int a[N];
int dp[N][N][N][2];
void solve() {
int n;
cin >> n;
int cnt1 = (n + 1) / 2, cnt2 = n / 2;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] & 1) {
cnt1--;
} else if (a[i]){
cnt2--;
}
}
memset(dp, 0x3f, sizeof dp);
if (a[1]) {
dp[1][0][0][a[1] & 1] = 0;
} else {
dp[1][1][0][0] = 0;
dp[1][0][1][1] = 0;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= i - j; k++) {
if (a[i]) {
dp[i][j][k][a[i] & 1] = min(dp[i - 1][j][k][0] + (a[i] & 1), dp[i - 1][j][k][1] + (1 - (a[i] & 1)));
} else {
dp[i][j][k][0] = min(dp[i - 1][j - 1][k][0], dp[i - 1][j - 1][k][1] + 1);
dp[i][j][k][1] = min(dp[i - 1][j][k - 1][0] + 1, dp[i - 1][j][k - 1][1]);
}
}
}
}
cout << min(dp[n][cnt2][cnt1][0], dp[n][cnt2][cnt1][1]) << endl;
}
signed main() {
ios;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}