【算法分析】
这题我做过类似的，基本思想是做垂线，然后向左右延伸。
算法步骤的思想如下：
枚举每一个点，然后尽量向上延伸，直到碰到墙壁或者坏了的点，然后将垂直的线段向左右尽量延伸，最后结果就在这M*N个极大子矩形当中。
这个算法很容易证明：如果是答案的子矩阵，那么它一定上下左右都被某个点（或边界）卡住，否则他还可以延伸就不是最大的了。然后这个算法把每一个格子当做是最大矩形的上顶点（即阻止它向上延伸的顶点），然后向下延伸任意长度的各种情况都枚举了，那么向左右延伸，就必然可以包含最优解。
最后利用DP的思想减少重复，复杂度达到O(RC)，使用滚动数组空间复杂度达到O(C)
【其它】
这题搞死我了，一直WA at 10，然后用pascal写了一遍，又是WA at 10
于是搞来搞去，最后发现原来是一个地方没有初始化，一交，终于AC，ORZ!!!
USACO终于圆满了，在此纪念一下
Chapter 1 DONE 2009.08.29 Getting started Chapter 2 DONE 2007.08.09 Bigger Challenges Chapter 3 DONE 2008.07.22 Techniques more subtle Chapter 4 DONE 2008.08.05 Advanced algorithms and difficult drills Chapter 5 DONE 2010.02.19 Serious challenges Chapter 6 DONE 2010.02.20 Contest Practice
这时间差好恐怖。。。
【CODE】
/*
ID:jie22221
TASK:rectbarn
LANG:C++
*/
#include
#define max(x,y) (x)>(y)?(x):(y)
const int INF=0x7FFFFFFF/5;
struct zb{int x,y;}s[31111];
int m,n,p,ans=0;
int u[2][3111],l[2][3111],r[2][3111],ll[3111],rr[3111];
bool v[2][3111];
void sort(int L,int R){
if (L>=R) return;
zb mid=s[(L+R)/2],tmp;
int i=L,j=R;
while (i
if (i<=j){
tmp=s[i]; s[i]=s[j]; s[j]=tmp;
i++; j–;
}
}
sort(L,j);
sort(i,R);
}
void init(){
memset(s,0,sizeof(s));
scanf("%d%d%dn",&m,&n,&p);
for (int i=0;i
sort(0,p-1);
for (int i=0;i<=n+1;i++){
v[0][i]=true;
l[0][i]=INF;
r[0][i]=INF;
}
}
void work(){
int si=0,i,j,R,pi,tmp;
for (R=1;R<=m;R++){
i=R&1; pi=i^1;
memset(v[i],false,sizeof(v[i]));
v[i][0]=true; v[i][n+1]=true;
for (j=1;j<=n;j++)
while (si
v[i][j]=true;
}
// deal ll
for (j=1;j<=n;j++)
if (!v[i][j])
if (v[i][j-1]) ll[j]=0;
else ll[j]=ll[j-1]+1;
// deal rr
for (j=n;j>=1;j–)
if (!v[i][j])
if (v[i][j+1]) rr[j]=0;
else rr[j]=rr[j+1]+1;
// dp
for (j=1;j<=n;j++)
if (!v[i][j]){
if (v[pi][j]){
u[i][j]=0;
l[i][j]=ll[j];
r[i][j]=rr[j];
}
else{
u[i][j]=u[pi][j]+1;
l[i][j]=min(ll[j],l[pi][j]);
r[i][j]=min(rr[j],r[pi][j]);
}
tmp=(l[i][j]+r[i][j]+1)*(u[i][j]+1);
if (tmp>ans)
ans=tmp;
}
}
}
int main(){
freopen("rectbarn.in","r",stdin);
freopen("rectbarn.out","w",stdout);
init();
work();
printf("%dn",ans);
}
