题解：P12349 [蓝桥杯 2025 省 B 第二场] 翻转硬币

CX_xiaoli · 2026-08-10 10:05:04 · 题解

把真实思考~~没想出来和看题解~~的过程总结了一下，希望对你有帮助。

题目大意

每个硬币的价值是其在 n\times m 的矩阵内四方向相邻的硬币中与它正反相同的硬币个数的平方。
可以选择翻转任意多的行以最大化总价值。

状态定义

首先这是一个 DP。如果设 dp_{i,j} 是前 i 行、前 j 列的最大总价值，会发现有后效性，得加上一个状态维度，而且状态转移也比较难得出，时间复杂度不好控制。所以设 dp_i 为前 i 行的最大总价值。

接下来我们发现第 i 行的总价值与第 i-1 行和第 i+1 行都有关系，所以只靠前 i 行的翻转情况是得不出前 i 行的总价值的。这时候就需要用到一个模板思想：设 dp_i 是前 i-1 行的最大总价值。这样我们只要通过转移来弄出（一部分是枚举靠近 i 的行的翻转状态，一部分是用已经算出的 dp 数组转移）前 i 行的翻转状态就可以计算出前 i-1 行的最大总价值。

正如之前所说，需要有状态机来确定靠近 i 的行的状态。那么状态机有几个，分别表示哪些行的状态呢？我们可以这样模板地考虑：第 i-1 行的总价值和第 i-2、第 i-1 和第 i 行的状态都有关系，所以我们在转移得出前 i-1 行的价值（即 dp_i）时一定会枚举这三行的翻转状态，而通过这三行的翻转状态要从一个状态转移到另一个状态，所以应该有两个状态机，分别表示第 i 行和第 i-1 行的翻转状态。这样根据循环的个数来导出状态的定义是一种很实用的方法，~~当且仅当这题一定是 DP~~。所以最终我们得出：设

dp_{i,j,k},i\in\{1,2,\dots,n\},j,k\in\{0,1\}

表示在第 i 行的翻转情况为 j，第 i-1 行的翻转情况为 k 时前 i-1 行的最大总价值。最终结果就要看 dp_{n+1} 的四种状态的最大值。

状态转移

在分析状态的时候我们已经提到，需要枚举三行的状态来转移，也就是从 dp_{i-1,x,y} 转移到 dp_{i,y,z}。注意这里的 y 应该是同一个状态，因为它们都代表了第 i-1 行。到这里已经很明显了，因为每个状态只有 0 和 1 两种取值，我们可以写出下面的状态转移方程：

dp_{i,y,z}=\max\{dp_{i-1,0,y}+q(i-1,0,y,z),dp_{i-1,1,y}+q(i-1,1,y,z)\}

其中 q(i,x,y,z) 表示在第 i-1,i,i+1 行的状态分别为 x,y,z 的时候第 i 行的总价值是多少，这是一个确定的值，所以可以预处理或者写成一个函数。如果你想省常数去比拼更优的解法，那你可以预处理数组 q_{i,x,y}，其中若 i 和 i-1 的翻转状态不同则 x=1，否则 x=0，y 同理。因为我们发现相邻的两行如果都被翻转，那么它们对对方的行间贡献（也就是 a_{i,j}=a_{i+1,j}）的数量与两行都没翻转是一样的，那么我们只要记录两行状态是否相同就行了，节约一维空间，dp 数组的状态定义也可以同样修改。但是如果你只是想用最简单、最好理解的方式 AC，就老老实实写一个 q 函数，考虑的会少一些。如果你没听懂，下面是清晰明了的代码。

代码实现与细节

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

const int N = 1005;
int n, m, a[N][N];
int dp[N][2][2];

int q(int i, bool x, bool y, bool z)
{
    int sum = 0;
    for (int j = 1; j <= m; j++) {
        int now = 0;
        if (j > 1 && a[i][j - 1] == a[i][j]) {
            now++;
        }
        if (j < m && a[i][j + 1] == a[i][j]) {
            now++;
        }
        if (i > 1) {
            if (x ^ y) {    // i和i-1状态不同
                if (a[i - 1][j] != a[i][j]) {
                    now++;
                }
            } else {
                if (a[i - 1][j] == a[i][j]) {
                    now++;
                }
            }
        }
        if (i < n) {
            if (y ^ z) {
                if (a[i + 1][j] != a[i][j]) {
                    now++;
                }
            } else {
                if (a[i + 1][j] == a[i][j]) {
                    now++;
                }
            }
        }

        sum += now * now;
    }
    return sum;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char x;
            cin >> x;
            a[i][j] = x - '0';
        }
    }

    for (int i = 2; i <= n + 1; i++) {
        dp[i][0][0] = max(dp[i - 1][0][0] + q(i - 1, 0, 0, 0), dp[i - 1][0][1] + q(i - 1, 1, 0, 0));
        dp[i][0][1] = max(dp[i - 1][1][0] + q(i - 1, 0, 1, 0), dp[i - 1][1][1] + q(i - 1, 1, 1, 0));
        dp[i][1][0] = max(dp[i - 1][0][1] + q(i - 1, 1, 0, 1), dp[i - 1][0][0] + q(i - 1, 0, 0, 1));
        dp[i][1][1] = max(dp[i - 1][1][0] + q(i - 1, 0, 1, 1), dp[i - 1][1][1] + q(i - 1, 1, 1, 1));
    }

    cout << max({dp[n + 1][0][0], dp[n + 1][0][1], dp[n + 1][1][0], dp[n + 1][1][1]});

    return 0;
}

注意你的 q 函数定义，在状态转移中要把每行的状态对应上，不要对应错。
如果你要压行，q 函数的异或判断可以用位运算去掉，但是实际没必要。
总结：如果 i 的价值和前后都有关系，设 dp_i 是前 i-1 个元素的最大总价值，然后枚举相邻 3 个元素的状态进行更新。

AC 记录，完结撒花！若本题解有助于君，恳留一赞！