自动搬运

查看原文

来自洛谷，原作者为

	_Violet_Evergarden 花无凋零之日,意无传递之时,爱情亘古不变,紫罗兰永世长存

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

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

以下是正文

来一发双倍经验

题意：

只需找出矩阵中最大的由 $0$ 构成的子矩阵。

思路：

我们只需要记录每个点左边有多少个连续的 $0$，然后在每个点遍历的时候加上最优性剪枝即可。见代码便可懂。

优化：

目前我们的时间复杂度还是超时的。那我们就用悬线法优化一下，悬线法就是我们对每个点从上往下遍历，用提前储存的左边有多少个 $0$ 来进行计算，最后再加上最优性的遍历即可。此时我们的的时间复杂度就无限趋近 $\mathcal{O}(N^2)$ 就可以拿下了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[2001][2001];
int b[2001][2001];
int ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		int m=0;
		for(int j=1;j<=n;j++){
			if(a[i][j]==0){
				m++;
				
			}
			else{
				m=0;
			}
			b[i][j]=m;//存左边有多少个连续的零 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int p=b[i][j];
			if(p==0){
				continue;
			}
			ans=max(p,ans);
			for(int k=i+1;k<=n;k++){
				p=min(p,b[k][j]);
				if(p==0||p*(n-i+1)<=ans){//最优性剪枝 
					break;
				}
				ans=max(p*(k-i+1),ans);
			}
		}
	}
	cout<<ans;
	return 0;
}