题解：使城市美丽的最小硬币数

题目回顾

我们有一个 $n \times n$ 的网格，每个格子 $(i, j)$ 有一个初始高度 $h_{i,j}$。有两种操作：

• 行操作：雇佣 A 公司的工人 $i$（花费 $a_i$），使第 $i$ 行所有建筑高度 $+1$。
• 列操作：雇佣 B 公司的工人 $j$（花费 $b_j$），使第 $j$ 列所有建筑高度 $+1$。

每名工人最多雇佣一次，即每行/每列最多执行一次操作。

目标是使最终网格满足：任意两个水平相邻的建筑高度不相等，任意两个垂直相邻的建筑高度也不相等。求最小总花费，或输出 $-1$ 表示不可能。

---

核心观察：行操作与列操作的独立性

设最终第 $i$ 行的高度增加量为 $r_i \in \{0,1\}$（$0$ 表示不雇佣 A 公司工人 $i$，$1$ 表示雇佣），第 $j$ 列的高度增加量为 $c_j \in \{0,1\}$。最终高度为：

$$H_{i,j} = h_{i,j} + r_i + c_j$$

考虑水平条件：要求 $H_{i,j} \neq H_{i,j+1}$，即

$$(h_{i,j} + r_i + c_j) \neq (h_{i,j+1} + r_i + c_{j+1}) $$

两边消去 $r_i$，得到

$$h_{i,j} + c_j \neq h_{i,j+1} + c_{j+1}$$

该条件与所有 $r_i$ 无关，只依赖于列操作 $c_j$ 的选择。

同理，垂直条件 $H_{i,j} \neq H_{i+1,j}$ 化简为

$$h_{i,j} + r_i \neq h_{i+1,j} + r_{i+1}$$

仅依赖于行操作 $r_i$ 的选择。

因此，水平条件和垂直条件是相互独立的！我们可以分别求出满足垂直条件所需的最小行操作花费，以及满足水平条件所需的最小列操作花费，最后相加即为答案。

---

垂直条件：行操作的 DP

我们首先解决垂直条件：确定哪些行需要执行操作，使得任意上下相邻的两个格子高度不相等，且总花费最小。

状态定义

令 $dp[i][x]$ 表示处理完前 $i$ 行（从第 $0$ 行到第 $i-1$ 行，按 $0$ 索引），且第 $i-1$ 行是否执行操作的状态为 $x$（$x=0$ 表示不操作，$x=1$ 表示操作）时的最小花费。若无法实现，则值为 $+\infty$。

初始状态

对于第一行（$i=0$）：

• 不操作：$dp[0][0] = 0$
• 操作：$dp[0][1] = a_0$

状态转移

考虑从第 $i-2$ 行转移到第 $i-1$ 行（$i \ge 1$）。假设第 $i-2$ 行的操作状态为 $y$，第 $i-1$ 行的操作状态为 $x$。此时两行的高度分别为：

• 上一行（第 $i-2$ 行）第 $j$ 列：$h_{i-2, j} + y$
• 当前行（第 $i-1$ 行）第 $j$ 列：$h_{i-1, j} + x$

垂直条件要求对于每一列 $j$，这两个值都不相等。即：

$$\forall j \in [0, n-1], \quad h_{i-2, j} + y \neq h_{i-1, j} + x $$

如果该条件满足，则可以从 $dp[i-1][y]$ 转移到 $dp[i][x]$：

• 若 $x=0$（当前行不操作），不需要额外花费：$$dp[i][0] = \min(dp[i][0], \ dp[i-1][y])$$
• 若 $x=1$（当前行操作），需加上 $a_{i-1}$：$$dp[i][1] = \min(dp[i][1], \ dp[i-1][y] + a_{i-1})$$

最终结果

所有行处理完毕后，满足垂直条件的最小行操作花费为：

$$\text{row\_cost} = \min(dp[n-1][0],\ dp[n-1][1])$$

---

水平条件：转化为行操作 DP

对于水平条件，我们需要选择列操作的子集，满足左右相邻格不等。这与垂直条件完全对称，只需将矩阵转置（行列互换），然后问题就变为：对转置后的矩阵，要求“上下相邻”（实际上对应原矩阵的左右相邻）不等，即处理列操作就像处理行操作一样。

假设转置后的矩阵为 $h'$，其中 $h'_{i,j} = h_{j,i}$。设列操作的花费数组为 $b$。我们对 $h'$ 调用与上面完全相同的 DP 函数，只是使用 $b$ 作为操作代价，得到的最小花费即为满足水平条件的列操作花费：

$$\text{col\_cost} = \text{solveHor}(n, h', b)$$

---

算法步骤

对于每组测试用例：

1. 读入 $n$，矩阵 $h$，行花费 $a$，列花费 $b$。
2. 计算行操作最小花费：
   • 调用 solveHor(n, h, a)，返回 $\text{row\_cost}$。
3. 转置矩阵 $h$ 得到 $h'$。
4. 计算列操作最小花费：
   • 调用 solveHor(n, h', b)，返回 $\text{col\_cost}$。
5. 令总花费 $\text{total} = \text{row\_cost} + \text{col\_cost}$。
   • 若 $\text{total} \ge \text{INF}$，则输出 $-1$（无解）。
   • 否则输出 $\text{total}$。

---

时间复杂度

DP 函数中，状态数 $O(n)$，对每个状态我们尝试上一行的两种状态，每次需要 $O(n)$ 检查两行所有列是否满足不等条件。因此单次 DP 复杂度为 $O(n^2)$。转置矩阵也是 $O(n^2)$。每组数据的总复杂度 $O(n^2)$。

题目保证所有测试用例的 $n$ 之和不超过 $1000$，最坏情况下 $\sum n^2 \le (1000)^2 = 10^6$，完全可行。

空间复杂度为 $O(n^2)$ 存储矩阵，或可优化为 $O(n)$ 但没必要。

---

参考代码

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

const long long INF = 1e18;

// 计算使得相邻行全部满足垂直条件的最小行操作花费
// h: 高度矩阵 (n x n), a: 每行的操作代价
long long solveHor(int n, vector<vector<int>>& h, vector<int>& a) {
    // dp[i][x]: 前 i+1 行，第 i 行操作状态为 x 的最小花费
    vector<vector<long long>> dp(n, vector<long long>(2, INF));
    dp[0][0] = 0;          // 第一行不操作
    dp[0][1] = a[0];       // 第一行操作

    for (int i = 1; i < n; ++i) {
        for (int x = 0; x < 2; ++x) {         // 当前行操作状态
            for (int y = 0; y < 2; ++y) {     // 上一行操作状态
                bool ok = true;
                // 检查两行所有列是否都不等
                for (int j = 0; j < n; ++j) {
                    if (h[i - 1][j] + y == h[i][j] + x) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    if (x == 0) {
                        dp[i][x] = min(dp[i][x], dp[i - 1][y]);
                    } else {
                        dp[i][x] = min(dp[i][x], dp[i - 1][y] + a[i]);
                    }
                }
            }
        }
    }

    return min(dp[n - 1][0], dp[n - 1][1]);
}

// 转置矩阵
void transpose(int n, vector<vector<int>>& h) {
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            swap(h[i][j], h[j][i]);
        }
    }
}

void test() {
    int n;
    cin >> n;

    vector<vector<int>> h(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> h[i][j];

    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    // 垂直条件：行操作
    long long rowCost = solveHor(n, h, a);

    // 水平条件：转置后用列操作当作行操作处理
    transpose(n, h);
    long long colCost = solveHor(n, h, b);

    long long total = rowCost + colCost;
    if (total >= INF) {
        cout << -1 << '\n';
    } else {
        cout << total << '\n';
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        test();
    }
    return 0;
}