最大全0子矩阵+最大全0子正方形
没啥区别 悬线法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// <1057.cpp> - 07/28/16 08:16:11 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=2010; const int INF=1e9; bool a[MAXN][MAXN]; int k[MAXN],l[MAXN],r[MAXN]; int n,m,ans1,ans2; void get(){ for(int j=1;j<=m;j++)k[j]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)k[j]=a[i][j]*(k[j]+1); for(int j=1;j<=m;j++){ if(!k[j])continue; for(l[j]=j;k[l[j]-1]>=k[j];l[j]=l[l[j]-1]); } for(int j=m;j;j--){ if(!k[j])continue; for(r[j]=j;k[r[j]+1]>=k[j];r[j]=r[r[j]+1]); ans1=max(ans1,min(k[j],r[j]-l[j]+1)); ans2=max(ans2,k[j]*(r[j]-l[j]+1)); } } } int main(){ n=gi(),m=gi(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)a[i][j]=gi()^(i+j)&1; get(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)a[i][j]^=1; get(); printf("%d\n%d",ans1*ans1,ans2); return 0; } |
说点什么