自动搬运

查看原文

来自洛谷，原作者为

	Binaerbaka To Achieve Your Value.

搬运于2025-08-24 22:29:10，当前版本为作者最后更新于2023-04-24 23:59:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

描述

这道题是一个较为细节的 dp 题目。

细节部分在于它足足有四个转移方程所以及其细节。

洛谷博客版。

题意

在给定网格 $0 1$ 中找出最大的 $I$ 形的 $0$ 部分，输出最大网格区块。

先前定义

我们需要用两类数组来方便转移。

1. $dp_{x,l,r,p}$ 数组来记录 $p$ 部分,其中 $x$ 是行数,同时为了节省空间我们可以只用两个数组交替使用，每次使用上一次的储存结果即可，记得初始化。

2. $f_{l,r,p}$ 数组来辅助计算 $dp$ 中 $P2$ 与 $P3$ 的值

注:为什么要利用新数组来辅助计算呢，因为在运行过程中，我们需要不断枚举每个 $l,r$ 区间的最大值来进行转移方程，若如此，复杂度将会达到惊人的 $O(n^4)$ ，但实际上这里的计算与 $dp$ 的计算是独立的，当前互相不干扰的，所以可以提前储存，来降低复杂度。

理解

由于 $I$ 的独特性质(上面部分大于中间部分，中间部分小于下面部分)所以我们需要去分类三种情况去讨论各自的转移方程。

• 上面部分 （$P1$） 可以直接在进行 $dp$ 的转移，无需用到第二个数组 所以它只要跑 $P1$ 循环 不必进行 $f$ 的更新。

• 中间部分 （$P2$） 需要利用 $f$ 数组辅助 $dp$ 转移，而且它转移需要符合如下规则：

  • $f_{l,r,1}$ 是由 $dp_{x,l,r,1}$ 向下转移的，由于 $P1$ 水平格子数一定大于 $P2$ ( $I$ 的上部分要出头)，所以它就应该往中间转移，则取 $\max(f_{l+1,r},f_{l,r+1})$ 并且与原 $dp$ 数组做比较，即方程为

  $f_{l,r,1}=\max(dp_{id,l,r,1},\max(f_{l-1,r,1},f_{l,r+1,1})$。

  • $f_{l,r,2}$ 是由 $dp_{x,l,r,2}$ 向下转移的，由于 $P2$ 水平格子数一定小于 $P3$ ( $I$ 的下部分要出头)，所以它就应该往两边转移，则取 $\max(f_{l+1,r},f_{l,r-1})$ 并且与原 $dp$ 数组做比较，即方程为

  $f_{l,r,2}=\max(dp_{id,l,r,2},\max(f_{l+1,r,2},f_{l,r-1,2})$。

• 下面部分 （$P3$) 与中间部分相似，但是它只要利用 $f$ 来求出当前 $dp$ 就可以直接求 $ans$ 值了 所以只需要跑 $P3$ 部分即可

• 额外：由于我们需要去来判断某一区间内是否是空的，可以利用前缀和来计算，只要 $sum_R-sum_{L-1} = 0$ 则为空。

利用图片与代码来方便理解。

不知道各位能不能理解。

由于 $P1$ 部分大于 $P2$ 部分，所以我们需要将 $L-1$ 与 $R+1$ 的 $f$ 部分转移到 $dp_{L,R}$ 中 因而有方程

$dp_{id,1,r,2}=\max(dp_{id,1,r,2},f_{l-1,r+1,1}+len)$。

同理 由于 $P2$ 部分小于 $P3$ 部分，所以我们的 $dp_{L,R}$ 的部分需要由 $L+1$ 和 $R-1$ 的 $f$ 部分中转移得到 因而有方程

$dp_{id,1,r,3}=\max(Dp_{id,1,r,3},f_{l+1,r-1,2}+len)$。

最后对 $dp_{id,l,r,3}$ 取一个最大值即为答案。

自此 所有的转移方程部分已经结束，下面便是代码。

Std

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2+5;
int n,m,id,x,ans;
int dp[2][maxn][maxn][4];
int sum[maxn];
int f[maxn][maxn][3];//用来辅助计算 p2 跟 p3 的最值。
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m;
	memset(f,-0x3f3f3f,sizeof(f));
	memset(dp,-0x3f3f3f,sizeof(dp));
	for(int i=1,x;i<=n;i++){
		for(int j=1,x;j<=m;j++)cin>>x,sum[j]=sum[j-1]+x;//维护前缀和。
		memset(dp[id],-0x3f3f3f,sizeof(dp[id]));//在“建立”完新数组之后 初始化。
		for(int p=3;p>=1;p--){
			for(int l=1;l<=m;l++){//遍历左区间
				for(int r=l;r<=m;r++){//遍历右区间
					if(sum[r]-sum[l-1]==0){
						int len=r-l+1;
						if(p==1)dp[id^1][l][r][1]=max(dp[id^1][l][r][1],0);//初始化数组 在跑 p1 时 初始化为 0 或保留原值。
						dp[id][l][r][p]=dp[id^1][l][r][p]+len;//如果先前数组有大于 0 的值，则继承并加上长度，否则不变。
						if(p==2)dp[id][l][r][2]=max(dp[id][l][r][2],f[l-1][r+1][1]+len);//方程 3 得。
						if(p==3)dp[id][l][r][3]=max(dp[id][l][r][3],f[l+1][r-1][2]+len);//方程 4 得。
					}
				}
			}
			if(p==1)
				for(int l=1;l<=m;l++)
					for(int r=m;r>=l;r--)
						f[l][r][1]=max(dp[id][l][r][1],
						max(f[l-1][r][1],f[l][r+1][1]));//方程 1 得。
			if(p==2)
				for(int l=m;l>=1;l--)
					for(int r=l;r<=m;r++)
						f[l][r][2]=max(dp[id][l][r][2],
						max(f[l+1][r][2],f[l][r-1][2]));//方程 2 得。
			if(p==3)
				for(int l=1;l<=m;l++)
					for(int r=1;r<=m;r++)
						ans=max(ans,dp[id][l][r][3]);//取最大值。
			
		}
		id^=1;//转换到新数组上。
	}
	cout<<ans;
	return 0;
}

祝大家早日 AC。

实在理解不了的话，记得手跑代码试试哦。