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

· · 题解

P12349 题解

思路

考虑动态规划。我们可以观察到，硬币翻转只与其上下的硬币是否翻转有关，与左右是否翻转无关，且每一行的硬币的贡献只与其上下行的贡献有关，我们可以考虑每一行的局部最优从而决定全局最优。

状态定义

由于每一行的贡献取决于其上下两行的贡献，所以我们必须枚举到第 i+1 行，才能求出第 i 行的最大贡献，那么，该怎么记录每一行的状态呢？可以想到，用 dp[i+1][j][k] 记录状态，其中 j 表示 i+1 行翻不翻，k 表示其 i 行翻不翻，我们用该式记录的是 i 行的最大值，已经有了第 i+1 和 i 行的状态了，怎么知道 i-1 行的状态呢？没错，dp[i][j][k] 中的 k 即是 i-1 行的状态。

转移方程

由于我们知道了 i-1 行和 i 行的状态，所以只要取 i-2 行的两个状态的最大值加上状态约束下的值就行了。某一状态的转移方程为：dp[i][0][0] = \max \left\{ \begin{aligned} &dp[i-1][0][1] + \operatorname{val}(i-1, 1, 0, 0), \\ &dp[i-1][0][0] + \operatorname{val}(i-1, 0, 0, 0) \end{aligned} \right\}。

代码思路

根据状态转移方程，枚举每一行四种状态的最大值，最后从最后一行的四种状态中选出最大值输出。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6;
int graph[1010][1010], dp[1010][2][2], n, m;
int dx[4] = {0,0,1,1}, dy[4] = {0,1,0,1};//四种状态
int com(int x, int pre, int now, int nex) //计算在状态约束下当前行的贡献，pre 表示前行约束，now 表示当前行，nex 表示下一行。
{
    int res = 0;
    for (int r = 1; r <= m; r++){
        int t = 0;
        if(graph[x][r] == graph[x][r - 1]) t++;
        if(graph[x][r] == graph[x][r + 1]) t++;
        if(x - 1 > 0)
            if(!(now == pre ^ graph[x][r] == graph[x-1][r]))
                t++;
        if(x + 1 <= n)
            if(!(now == nex ^ graph[x][r] == graph[x+1][r]))
                t++;
        res += t* t;
    }
    return res;
}
int main()
{
    cin >> n >> m;
    memset(graph, -1, sizeof(graph)); 
    for(int i = 1; i <= n; i++){   //建图
        string t; cin >> t;
        for (int j = 1; j <= m; j++)
            graph[i][j] = t[j - 1] - '0';
    }
    for (int i = 0; i < 4; i++)  //初始化dp数组
        dp[2][dx[i]][dy[i]] = com(1,0,dy[i],dx[i]);
    for (int i = 3; i <= n + 1; i++){  //枚举每一行
        for (int j = 0; j < 4; j++)  //枚举四种状态
            dp[i][dx[j]][dy[j]] = max(dp[i-1][dy[j]][0] + com(i-1,0,dy[j],dx[j]), dp[i-1][dy[j]][1] + com(i-1,1,dy[j],dx[j]));
    }
    cout << max({dp[n + 1][0][0],dp[n + 1][0][1],dp[n + 1][1][0],dp[n + 1][1][1]});
    return 0;
 }