跳转至

CCPC 2026 贵州邀请赛 B. 娄山关扫雷 题解

https://codeforces.com/gym/695551/problem/B

本场最具争议的一道题，三个人拼尽全力两个半小时没能战胜，~~后面发现是道错题。~~

题目大意

给定 \(n\times n\) 的地雷图，初始全为空格，需要放置恰好 \(k^2\) 枚地雷（一格最多一枚）。

定义：

  • \(\bar{A}\)：地雷图 \(A\) 的反图（雷和空格互换）
  • \(S(A)\)：图 \(A\) 中所有空格的数字之和（每个数字 \(=\) 周围 \(8\) 格地雷数）

求 \(|S(A)-S(\bar{A})|+S(A)+S(\bar{A})\) 的最小值。

题目分析

官方题解 B. 娄山关扫雷

一、公式化简

\(S(A)=S(\bar{A})\) 恒成立，原式等价于求 \(2\cdot S(A)\) 的最小值。

\(S(A)\) 本质是雷与空格的 \(8\) 邻域相邻对数。

二、核心策略

要最小化相邻对数，地雷应尽可能聚拢，并尽量贴在角落以减少暴露边界。考虑某一行中固定数量的地雷。如果这一行的地雷不是连续的，那么中间至少存在多个“地雷—空格”交界，从而不会优于把地雷压缩成一个连续段。如果连续段不贴边，那么它左右两侧都会产生边界；将其移动到边界处后，行内边界不会增加。对于相邻两行，\(8\) 邻接只与列差不超过 \(1\) 的格子有关。将每一行的地雷向同一侧压缩，不会增加相邻两行之间的“地雷—空格”边数。

因此，存在一个最优方案满足：每一行的地雷都是该行的一个前缀。

三、代价拆分

对于一行前 \(x\) 个格子为地雷：\(rowCost(x) = 1 (0<x<n)\)，而 \(x=0\) 或 \(x=n\) 时为 \(0\)。

对于相邻两行，设上一行有 \(a\) 个地雷，下一行有 \(b\) 个地雷，预处理 \(trans(a,b)\) 表示这两行之间纵向和斜向的“雷—空”相邻对数。因为 \(8\) 邻域中相邻两行的格子只会在列差不超过 \(1\) 时相邻，所以 \(trans(a,b)\) 可以直接暴力计算。

四、动态规划求解

设 \(dp[s][x]\) 表示已经处理完若干行，总共放了 \(s\) 个地雷，并且最后一行放了 \(x\) 个地雷时，当前最小的 \(S(A)\)。枚举下一行放 \(y\) 个地雷：

\[dp'[s + y][y] = \min(dp'[s + y][y], dp[s][x] + rowCost(y) + trans(x, y))\]

初始化第一行 \(dp[x][x] = rowCost(x)\)，最终 \(ans = 2\times\min_{x}dp[k^2][x]\)。

复杂度为 \(O(n^3k^2)\)。

完整代码

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

const int N = 55;

int n, m;
int cost[N], tran[N][N];
int old_dp[N*N][N], new_dp[N*N][N];
int ans = INT32_MAX;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    m = m * m;

    for (int i = 1; i < n; i++) {
        cost[i] = 1;
    }
    cost[0] = cost[n] = 0;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            int cnt = 0;
            int row_i[N] = {0}, row_j[N] = {0};
            for (int k = 0; k < i; k++) row_i[k] = 1;
            for (int k = 0; k < j; k++) row_j[k] = 1;

            for (int k = 0; k < n; k++) {
                if (row_i[k] != row_j[k]) cnt++;                  // 正下
                if (k > 0 && row_i[k] != row_j[k - 1]) cnt++;     // 左下
                if (k + 1 < n && row_i[k] != row_j[k + 1]) cnt++; // 右下
            }
            tran[i][j] = cnt;
        }
    }

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            old_dp[i][j] = INT32_MAX;
        }
    }

    for (int row = 1; row <= n; row++) {
        if (row == 1) {
            for (int i = 0; i <= n; i++) {
                old_dp[i][i] = cost[i];
            }
            continue;
        }

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                new_dp[i][j] = INT32_MAX;
            }
        }

        for (int s = 0; s <= m; s++) {
            for (int x = 0; x <= n; x++) {
                if (old_dp[s][x] == INT32_MAX) continue;
                for (int y = 0; y <= n; y++) {
                    if (s + y > m) continue;
                    new_dp[s + y][y] = min(new_dp[s + y][y], old_dp[s][x] + cost[y] + tran[x][y]);
                }
            }
        }

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                old_dp[i][j] = new_dp[i][j];
            }
        }
    }

    for (int i = 0; i <= n; i++) {
        ans = min(ans, old_dp[m][i]);
    }
    cout << 2 * ans << endl;

    return 0;
}