自动搬运

查看原文

来自洛谷，原作者为

	KK_luck **

搬运于2025-08-24 23:14:50，当前版本为作者最后更新于2025-04-27 11:56:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
 }