前置知识

简化题意

在一个 $n \times n$ 的正方形内找到最大的由 $0$ 组成的子矩形的面积。

解法

令 $f_{i,j}(1 \le i,j \le n)$ 表示从 $(1,j)$ 到 $(i,j)$ 中以 $(i,j)$ 结尾的均为 $0$ 的子串长度，即 $(i,j)$ 上面可延伸的最大距离（子矩形的长）。

用单调栈的第一维存储子矩形的长，第二维存储子矩形的宽。考虑依次枚举每一行和每一列，进行出入栈的操作。当枚举到 $(i,j)$ 的位置时，记录子矩形的宽 $num$，有如下操作：

对于栈中原来的元素中大于当前的长 $f_{i,j}$，要将其弹出栈，计数器 $num$ 加 $1$。
- 子矩形的宽为弹出栈的元素个数。
- 其所形成的子矩形面积为 $num \times $ 栈中当前的元素。
将所得到的长 $f_{i,j}$ 和宽 $num$ 入栈。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define sort stable_sort 
#define endl '\n'
int f[2001][2001];
int main()
{
	int n,pd,i,j,ans=0,num;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			cin>>pd;
			if(pd==0)
			{
				f[i][j]=f[i-1][j]+1;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		stack<pair<int,int> >s;
		s.push(make_pair(f[i][1],1));
		for(j=2;j<=n;j++)
		{
			num=0;
			while(s.empty()==0&&s.top().first>f[i][j])
			{
				num+=s.top().second;
				ans=max(ans,num*s.top().first);
				s.pop();
			}
			s.push(make_pair(f[i][j],num+1));
		}
		num=0;
		while(s.empty()==0)
		{
			num+=s.top().second;
			ans=max(ans,num*s.top().first);
			s.pop();
		}
	}
	cout<<ans<<endl;
	return 0;
}