自动搬运

查看原文

来自洛谷，原作者为

	zzy_zzy 勇敢去做爱做的事 || 孻龒

搬运于2025-08-24 23:17:21，当前版本为作者最后更新于2025-07-04 10:46:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

鲜花

期末考完，作业全免，心情很好，故作此文。

题解

看到这种求矩阵路径最大的题，先考虑 dp。

但是对于这道题只设置一个状态显然是不够的，因为你无法使用一个状态来处理黑色格子“延迟加”这种东西，因此考虑设两个状态：

• $dp_{i,j,1}$ 表示 dp 到 $(i,j)$ 格子的真实最大值。
• $dp_{i,j,2}$ 表示 dp 到 $(i,j)$ 格子的虚假最大值。即走到黑格子时无论怎样都把当前贡献加上。

这样，转移就很简单了，遇到白格子的时候，分讨一下上一个格子的颜色；遇到黑格子的时候，记得比较的是 dp2 的大小。

不懂的参见代码：

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010];
bool b[1010][1010];
int dp1[1010][1010];
int dp2[1010][1010];

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>b[i][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(b[i][j]){
				if(b[i][j-1]){
					dp1[i][j]=dp1[i][j-1]+a[i][j];
					dp2[i][j]=dp2[i][j-1]+a[i][j];
				}
				else{
					dp1[i][j]=dp1[i][j-1];
					dp2[i][j]=dp2[i][j-1];
				}
				if(b[i-1][j]){
					dp1[i][j]=max(dp1[i][j],dp1[i-1][j]+a[i][j]);
					dp2[i][j]=max(dp2[i][j],dp2[i-1][j]+a[i][j]);
				}
				else{
					dp1[i][j]=max(dp1[i][j],dp1[i-1][j]);
					dp2[i][j]=max(dp2[i][j],dp2[i-1][j]);
				}
			}
			else{
				if(dp2[i][j-1]>dp2[i-1][j]){
					dp1[i][j]=dp2[i][j-1];
					dp2[i][j]=dp1[i][j]+a[i][j];
				}
				else{
					dp1[i][j]=dp2[i-1][j];
					dp2[i][j]=dp1[i][j]+a[i][j];
				}
			}
		}
	}
	cout<<dp1[n][m];
	return 0;
}