CF1990D Grid Puzzle 题解

题意回顾

有一个 $n \times n$ 的网格，第 $i$ 行前 $a_i$ 个格子是黑色，其余为白色。两种操作：

• 操作 A：将一整行染成白色，花费 $1$；
• 操作 B：将一个 $2 \times 2$ 的子网格染成白色，花费 $1$。

求将所有黑色格子染白的最小操作次数。$1 \le n \le 2\cdot 10^5$，$0 \le a_i \le n$。

核心观察

1. 每行的黑色格子是从第 $1$ 列开始的连续前缀。如果 $a_i > 4$，直接对该行使用一次操作 A 总是最优的——因为若用操作 B，至多覆盖左侧的 $2$ 列或 $4$ 列，剩余部分仍需额外操作，不如一次操作 A。
2. 因此我们只需对 $a_i \le 4$ 的行精细处理，$a_i > 4$ 的行直接操作用 A，代价 $+1$，并等价于 $a_i = 0$（后续不再需要考虑该行的黑格）。

DP 状态设计

处理前 $i$ 行，定义三个状态（均表示前 $i$ 行全部变白）：

• 状态 0：第 $i$ 行已全部覆盖，且没有操作 B 延伸到第 $i+1$ 行。
• 状态 1：第 $i$ 行已全部覆盖，且有一个操作 B 覆盖了本行的左两块（列 $1$–$2$），并延伸到第 $i+1$ 行。
• 状态 2：第 $i$ 行已全部覆盖，且有一个操作 B 覆盖了本行的右两块（列 $3$–$4$），并延伸到第 $i+1$ 行；而本行的左两块是由第 $i-1$ 行延伸下来的操作 B 覆盖的。

操作 B 的放置总是按列顺序：先覆盖列 $1$–$2$（左块），再覆盖列 $3$–$4$（右块）。不再考虑更靠右的块，因为 $a_i \le 4$。

转移方程

设 $f[i][0/1/2]$ 表示前 $i$ 行处理完，且第 $i$ 行处于对应状态的最小花费。

初始化（第 $1$ 行）

• $f[1][0] = [a_1 > 0]$（若 $a_1>0$ 则必须操作 A，否则为 $0$）。
• 若 $a_1 \le 2$，可以发起一个左块操作 B：$f[1][1] = 1$。

递推（$2 \le i < n$）

f[i][0] = f[i-1][0] + !!a[i];
if (a[i] <= 2) {
    f[i][0] = min(f[i][0], f[i-1][1]);        // 上一行延伸的左块覆盖了本行
    f[i][1] = f[i-1][0] + 1;                  // 本行发起左块操作 B
}
if (a[i] <= 4) {
    f[i][1] = min(f[i][1], f[i-1][2] + 1);    // 上一行延伸右块，本行补左块
    f[i][2] = f[i-1][1] + 1;                  // 上一行延伸左块，本行补右块
}

转移解释：

• $f[i][0]$：基础是上一行状态 $0$ 再加本行操作 A（若 $a_i>0$）。若 $a_i \le 2$，则上一行状态 $1$ 延伸下来的左块已覆盖本行全部黑格，无需额外操作。
• $f[i][1]$：本行发起一个左块操作 B，要求上一行状态 $0$ 且 $a_i \le 2$。也可由上一行状态 $2$ 补一个左块操作 B（当 $a_i \le 4$）：上一行延伸了右块，本行左块空缺，再花费 $1$ 补上。
• $f[i][2]$：上一行状态 $1$ 延伸左块到本行，本行再花费 $1$ 补一个右块操作 B（要求 $a_i \le 4$）。

结尾（第 $n$ 行）

最后一行不能向 $n+1$ 延伸：

• 若第 $n-1$ 行状态 $0$：本行只能操作 A（若 $a_n>0$）或不操作，答案为 $f[n-1][0] + [a_n>0]$。
• 若第 $n-1$ 行状态 $1$ 且 $a_n \le 2$：上一行的左块操作 B 已覆盖本行，答案为 $f[n-1][1]$。

最终答案取两者较小值。

复杂度

• 时间复杂度 $O(n)$。
• 总空间 $O(n)$ 或滚动数组 $O(1)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, INF = 1e9;

int _, n, a[N], f[N][3], ans;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> _;
    while (_--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i], f[i][0] = f[i][1] = f[i][2] = INF;

        if (n == 1) {
            cout << !!a[1] << '\n';
            continue;
        }

        f[1][0] = !!a[1];
        if (a[1] <= 2) f[1][1] = 1;

        for (int i = 2; i < n; i++) {
            f[i][0] = f[i - 1][0] + !!a[i];
            if (a[i] <= 2) {
                f[i][0] = min(f[i][0], f[i - 1][1]);
                f[i][1] = f[i - 1][0] + 1;
            }
            if (a[i] <= 4) {
                f[i][1] = min(f[i][1], f[i - 1][2] + 1);
                f[i][2] = f[i - 1][1] + 1;
            }
        }

        ans = f[n - 1][0] + !!a[n];
        if (a[n] <= 2)
            ans = min(ans, f[n - 1][1]);
        cout << ans << '\n';
    }
    return 0;
}