既然要求最大01子矩阵,那么把应该为0的位置上的数取反,这样就变成求最大子矩阵
最大子矩阵可以用单调栈
#include<stdio.h> #include<string.h> #include<algorithm> #define maxn 2005 using namespace std; int n,m,map[maxn][maxn],ans1,ans2,l[maxn],r[maxn],d[maxn],t; int main(){ scanf("%d%d", &n, &m); ; i<=n; i++) ; j<=m; j++){ scanf("%d", &map[i][j]); ) map[i][j]^=; } ; i<=n; i++){ //黑为奇数行列 ; j<=m; j++){ l[j]=r[j]=j; if (map[i][j]) d[j]++; ; } ; j<=m; j++) ]>=d[j]) l[j]=l[l[j]-]; ; j--) ]>=d[j]) r[j]=r[r[j]+]; ; j<=m; j++){ t=min(d[j],r[j]-l[j]+); ans1=max(ans1,t*t); ans2=max(ans2,d[j]*(r[j]-l[j]+)); } } memset(d,,sizeof(d)); ; i<=n; i++){ //白为奇数行列 ; j<=m; j++){ l[j]=r[j]=j; if (!map[i][j]) d[j]++; ; } ; j<=m; j++) ]>=d[j]) l[j]=l[l[j]-]; ; j--) ]>=d[j]) r[j]=r[r[j]+]; ; j<=m; j++){ t=min(d[j],r[j]-l[j]+); ans1=max(ans1,t*t); ans2=max(ans2,d[j]*(r[j]-l[j]+)); } } printf("%d\n%d\n", ans1, ans2); ; }