了解一下悬线法解决最大子矩阵面积问题
//悬线法适用于在一个矩形内,而且有障碍物的情况下,求最大的子矩形面积
//悬线法只要处理上、左、右之间的关系,因为我们直接设了一行
//本人感觉悬线法和贡献法有点类似,只不过扩展成二维了
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 3010;
char str[N][N];
int l[N][N],r[N][N];//左、右
int h[N][N];//高度
int n,m,p;
int main(){
cin>>n>>m>>p;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
str[i][j]='F';
}
}
while(p--){
int x,y;
cin>>x>>y;
str[x][y]='M';
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(str[i][j]=='F')h[i][j]=1;
l[i][j]=r[i][j]=j;//最远到达的位置
}
}
for(int i=1;i<=n;i++){//处理每一行的左、右
for(int j=2;j<=m;j++){
if(str[i][j]=='F'&&str[i][j-1]=='F'){//处理左
l[i][j]=l[i][j-1];
}
}
for(int j=m-1;j>=1;j--){
if(str[i][j]=='F'&&str[i][j+1]=='F'){//处理右
r[i][j]=r[i][j+1];
}
}
}
//处理上
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(str[i][j]=='F'&&str[i-1][j]=='F'){
h[i][j]=h[i-1][j]+1;
r[i][j]=min(r[i][j],r[i-1][j]);//也要看上面能到哪里
l[i][j]=max(l[i][j],l[i-1][j]);
}
if(str[i][j]=='F')res=max(res,h[i][j]*(r[i][j]-l[i][j]+1));
}
}
cout<<res;
return 0;
}
very good