這題好像很早之前就看到過。。。那時候我還只會玩腳丫子,做這題完全像SB一樣,記得那時我做了一會就放棄了。
如今看到這題感覺好做多了,此題預處理很巧妙,我們看一個棋盤,它的所有黑點的行標奇偶性都相同,列標的奇偶性也都相同。白點一樣。
於是我們就可以預處理下,對於所有行標和列標奇偶性相同的點,保持它們的顏色不變,奇偶性不相同的點,反轉它們的顏色,於是預處理後,我們要找的矩形在整個大棋盤中的顏色一定是一樣的。
然後直接套用最大全0/1子矩陣就OK了。
#include#include #include #include #define MAXN 2200 using namespace std; int n,m; int map[MAXN][MAXN]; int h[MAXN],l[MAXN],r[MAXN]; int work1(int clr) //求最大全clr色的子矩陣(必須是正方形) { int maxSqr=0; memset(h,0,sizeof(h)); memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(map[i][j]==clr) h[j]++; else h[j]=0; } for(int j=1;j<=m;j++) { l[j]=j; while(l[j]>1&&h[l[j]-1]>=h[j]) l[j]=l[l[j]-1]; } for(int j=m;j>=1;j--) { r[j]=j; while(r[j] =h[j]) r[j]=r[r[j]+1]; } for(int j=1;j<=m;j++) { int nowsqr=min(h[j],r[j]-l[j]+1); nowsqr*=nowsqr; if(nowsqr>maxSqr) maxSqr=nowsqr; } } return maxSqr; } int work2(int clr) //求最大全clr色的子矩陣(不限於正方形) { int maxSqr=0; memset(h,0,sizeof(h)); memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(map[i][j]==clr) h[j]++; else h[j]=0; } for(int j=1;j<=m;j++) { l[j]=j; while(l[j]>1&&h[l[j]-1]>=h[j]) l[j]=l[l[j]-1]; } for(int j=m;j>=1;j--) { r[j]=j; while(r[j] =h[j]) r[j]=r[r[j]+1]; } for(int j=1;j<=m;j++) { if(h[j]*(r[j]-l[j]+1)>maxSqr) maxSqr=h[j]*(r[j]-l[j]+1); } } return maxSqr; } int main() { scanf(%d%d,&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int clr; scanf(%d,&clr); if(i%2==j%2) map[i][j]=clr; else map[i][j]=1-clr; } printf(%d %d ,max(work1(1),work1(0)),max(work2(1),work2(0))); return 0; }
??