程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [BZOJ 1057][ZJOI 2007]棋盤制作(最大全0/1子矩陣)

[BZOJ 1057][ZJOI 2007]棋盤制作(最大全0/1子矩陣)

編輯:C++入門知識

[BZOJ 1057][ZJOI 2007]棋盤制作(最大全0/1子矩陣)


 

這題好像很早之前就看到過。。。那時候我還只會玩腳丫子,做這題完全像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;
}

 

??

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved