随笔-141  评论-9  文章-3  trackbacks-0

题意:求最大子矩阵。

设h[i,j]是点(i, j)向上的最长距离,l[i,j]是点(i, j)向左的最长距离,r[i,j]是点(i, j) 向右的最常距离,

点(i, j)处的矩形面积 = h[i, j]*(l[i, j]+r[i, j]-1)

h[i, j] = h[i-1,j]+1  ( 点(i, j)是好的)
h[i, j] = 0              ( 点(i, j)是坏的)

l[i, j] = min( l[i-1, j] , k) ( 点(i, j)是好的)
l[i, j] = 0                       ( 点(i, j)是坏的)

r[i, j] = min(l[i-1, j], k) ( 点(i, j)是好的)
r[i, j] = 0                     ( 点(i, j)是坏的)


/*
ID: lorelei3
TASK: rectbarn
LANG: C++
*/


#include 
<fstream>

using namespace std;

const int MAX = 3005;

ifstream fin(
"rectbarn.in");
ofstream fout(
"rectbarn.out");

bool map[MAX][MAX];
int h[MAX], l[MAX], r[MAX];
int R,C,P,ans;

void input(){
    
int x,y;
    fin
>>R>>C>>P;
    
for(int i=0; i<P; ++i){
        fin
>>x>>y;
        map[x][y]
=true;
    }

}


inline 
int min(int a, int b){
    
if (a<&& a!=0
        
return a;
    
return b;
}


inline 
int max(int a, int b){
    
return a>b?a:b;
}

void dp(){
    
int i,j,k;
    
for(i=1; i<=R; ++i){
        k
=0;
        
for(j=1; j<=C; ++j){
            
if(!map[i][j]){
                h[j]
=h[j]+1;
                l[j]
=min(l[j], ++k);
            }
else
                h[j]
=0, l[j]=0, k=0;
        }


        k
=0;
        
for(j=C; j>=1--j){
            
if(!map[i][j]){
                r[j]
=min(r[j], ++k);
                ans
=max(ans, h[j]*(l[j]+r[j]-1));
            }
else
                r[j]
=0, k=0;
        }

    }

}


void output(){
    fout
<<ans<<endl;
}


int main(){
    
    input();

    dp();

    output();

    
return 0;
}
posted on 2011-02-18 15:43 小阮 阅读(601) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理