题意：求最大子矩阵。
设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<b && 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
小阮 阅读(579)
评论(0) 编辑 收藏 引用 所属分类:
USACO