题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1057
题意：最大相邻不同子矩形/子正方形。
从第一页开始的 BZ 刷水日常。
将棋盘黑白染色，正反各来一遍，即最大全 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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 2010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[N][N],b[N][N],c[N][N]; int ans,ans2,Ans,Ans2; int stk[N],top,l[N],r[N]; void solve() { memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(b[i][j]==1)c[i][j]=c[i-1][j]+1; for(int i=1;i<=n;i++) { for(int j=1;j<=m+1;j++) { while(top&&c[i][stk[top]]>c[i][j])r[stk[top]]=j,top--; l[j]=stk[top]+1; stk[++top]=j; } int len; for(int j=1;j<=m;j++) { len=r[j]-l[j]; if(len<0)continue ; ans=max(ans,c[i][j]*len); int mn=min(len,c[i][j]); ans2=max(ans2,mn*mn); } top=0; } } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)a[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)b[i][j]=((i+j)&1)?a[i][j]^1:a[i][j]; solve();Ans=ans,Ans2=ans2;ans=0,ans2=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)b[i][j]^=1; solve(); Ans=max(Ans,ans),Ans2=max(Ans2,ans2); printf("%d\n",Ans2); printf("%d\n",Ans); } |
Comments | NOTHING