[UASCO 6.1.2 Serious challenges]动态规划

【算法分析】

这题我做过类似的，基本思想是做垂线，然后向左右延伸。

算法步骤的思想如下：

枚举每一个点，然后尽量向上延伸，直到碰到墙壁或者坏了的点，然后将垂直的线段向左右尽量延伸，最后结果就在这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 #include #define min(x,y) (x)<(y)?(x):(y)
#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        while (s[i].x        while (s[j].x>mid.x || s[j].x==mid.x && s[j].y>mid.y) j–;
        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      scanf("%d%dn",&s[i].x,&s[i].y);
    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

              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);
}