CF2225C 题解

· · 题解

传送门：洛谷 CF2225C Red-Black Pairs | Codeforces C. Red-Black Pairs
更佳的阅读体验：CF2225C 题解

简要题意：给你一个 2 \times n 的网格，每个格子涂成红色或黑色，要求重新涂色最少数量的格子，使得所有格子能分成 n 对，每对格子颜色相同且相邻，求这个最小重新涂色数。\sum n \le 2 \times 10^5。

只有两行，所以所有可能的匹配方式就只有两种，也就是横着或者竖着的两格。匹配时如果这两格的颜色不相同，就产生 1 的代价，否则匹配的代价为 0。

此时问题变成了，我们需要找到一种匹配方式，使得所有格子都被匹配且代价最小。

考虑 DP。我们定义 f_i 表示匹配完前 i 列的最小总代价。转移时就只需要考虑，如果竖着匹配一次，那就匹配当前的这一列。或者横着匹配两次，匹配当前一列和前面的一列。

我们可以提前预处理出竖着匹配和横着匹配的代价 cost_1 和 cost_2：

\begin{cases} \text{cost}_{1, i} = [a_{1, i} \ne a_{2, i}] \\ \text{cost}_{2, i} = [a_{1, i} \ne a_{1, i + 1}] + [a_{2, i} \ne a_{2, i + 1}] \end{cases}

其中 [P] 表示命题 P 为真时值为 1，否则为 0。

于是我们就得到了转移方程。

f_i = \min \{ f_{i - 1} + \text{cost}_{1, i}, f_{i - 2} + \text{cost}_{2, i - 1} \}

时间复杂度 O(n)。

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

const int N = 2e5 + 10, M = 5;
int t, n, f[N], cost[M][N];
char c[M][N];

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        fill(f + 1, f + n + 1, 0);
        fill(cost[1] + 1, cost[1] + n + 1, 0);
        fill(cost[2] + 1, cost[2] + n + 1, 0);
        cin >> n >> c[1] + 1 >> c[2] + 1;
        for (int i = 1; i <= n; ++i) {
            cost[1][i] = c[1][i] != c[2][i];
            cost[2][i] = (c[1][i] != c[1][i + 1]) + (c[2][i] != c[2][i + 1]);
        } f[1] = cost[1][1];
        for (int i = 2; i <= n; ++i)
            f[i] = min(f[i - 1] + cost[1][i], f[i - 2] + cost[2][i - 1]);
        cout << f[n] << '\n';
    } return 0;
}