bzoj 1910 [CTSC2002] Award 颁奖典礼 题解【DP】【前缀和】

作者: wjyyy 分类: DP,前缀和,区间DP,区间统计,解题报告 发布时间: 2018-07-21 23:10

点击量:12

 

   清奇的前缀和优化。

 

Description

IOI2002的颁奖典礼将在YONG-IN Hall隆重举行。人们在经历了充满梦幻的世界杯之后变得更加富于情趣。为了使颁奖典礼更具魅力,有人建议在YONG-IN Hall中搭建一个I字型的颁奖台,以此代表信息学Informatics。考虑到比赛的赞助商们可能要在YONG-IN Hall中摆设了许多展示台,他们可能不愿意移动展示台的位置。你作为IOI2002的金牌得主自然地成为了他们求助的对象。 YONG-IN Hall是一个矩形的网格区域。每个赞助商的展示台都占据了若干个单位网格。I型颁奖台将正向搭建,且平行于YONG-IN Hall的边缘。I型颁奖台是由三个矩形相接叠成的,其中上方和下方的矩形的两侧必须都超出中间的矩形,否则将被误解成T, L, J等字母。例如: 。 这是两个合法的I型颁奖台,而以下三种情况均不合法:  希望你编程寻找面积最大的I型颁奖台,使其不覆盖任何展示台。

Input

第一行包含两个正整数n, m(1<=n,m<=200),分别表示YONG-IN Hall的矩形网格区域的行数和列数。以下n行每行包含m个数字,非0即1,每个数字描述一个单位网格,1表示该单位网格存在展示台,0表示该单位网格不存在展示台。

Output

仅包含一个正整数,表示最大的I型颁奖台的面积。如果不存在合法的I型颁奖台,则输出0。

Sample Input

6 8
1 1 1 1 1 0 0 1
1 0 0 0 0 1 1 1
1 0 0 0 0 0 1 1
1 0 1 0 1 0 1 0
1 0 0 0 0 0 0 1
1 1 0 0 0 1 0 1

Sample Output

15

HINT

 

题解:

   第一眼看到这种题,首先想到的就是枚举合法矩形,再看能不能拼接。但是当0很多时,矩形个数会达到\(\frac{n(n+1)}2\times \frac{m(m+1)}2\),再来³的枚举的当然吃不消,因此我们要灵活考虑DP。

 

   我们可以试着用f[u][d][l][r][t]来存上边界为u,下边界为d,左边界为l,右边界为r,此时为第t部分。我们定义一个”I”的三部分分别为:

   那么t=0时,对应最上面一部分;t=1时对应中间一部分;t=2时对应下面一部分。而我们的顺序是从上往下做,因此前两维可以滚掉,不过第二维不滚掉对空间没有影响,所以我还是保留了。f[i][l][r][t]就代表第i行左端点为l,右端点为r时,各种情况解的最大值。注意下文中t对应的也是第t+1部分。

 

   对于区域①,我们枚举左右端点l,r,如果这个区间的数据全部是0,就转移上面这一区间的第一部分的状态,并加上区间长度。同时,考虑如果这一区间作为第二部分时,上面一层需要满足什么情况。这里最暴力的做法就是枚举l’严格小于当前l,枚举r’严格大于当前r,如果它有第一部分,就把它的第一部分转移过来加上当前区间长度;不要忘了转移上一层为第二部分的情况。第三部分也一样,枚举l’严格大于当前l,枚举r’严格小于当前r,做类似的转移。一个状态如果有多个转移来源记得取自己的max。

 

   对于上面这一部分来说,每次枚举的时间复杂度是\(O(m^4)\)的,整个程序的时间复杂度是\(O(nm^4)\),对于200的数据而言,除非用玄学bitset是过不了的。

 

   不过可以联想一下,如果l,r∈[l’,r’],那么当状态转移为l’,r’时,l,r也可以做出贡献,因此我们可以利用前缀和的思想,令g[l][r][t]表示f[上一层][i=l…r][j=i…r][c]中的最大值,这里计算的复杂度是\(O(m^2)\),不过它是独立的,也就只产生了\(O(nm^2)\)的复杂度。那么这里怎么算呢?我们参考这样一个图:

   对于第i行的一个区间[l’,r’]部分t的最大值,实际上是\(\max\limits_{l\in [l’,r’],r\in [l,r’]}f[i-1][l][r][t]\),上图的右下角。对于这个max,我们只需要一种类似区间DP或前缀和的方法,求出RMQ。也就是在上述不同部分之间的转移时,需要用到这种前缀和DP的技巧。介绍的是以②向③转移时合法的RMQ,注意这时是需要l’+1和r’-1这个区间的,因为两边都要外凸:)。在上图右下角,因为是从l=r向l’和r’方向扩展,所以枚举顺序是l降序,r升序(详细实现可以看代码)。对于①②部分转移就是图左上角,不过区间是l∈[0,l’],r∈[r’,m](实际过程中l’,r’取开),这样让l从0向l’枚举,让r从m向r’枚举,就包含了所有情况,也就是l升序,r降序。

 

   而这个最大值前缀和在上图中因为对于各个l≤r的点都要有效,所以也就是上一段所说的那样枚举。简单撕烤思考过后会发现,是沿对角线方向向A点枚举,因此就可以理解枚举过程中每个状态都是合法的了。

 

   所以在不同部分的转移过程中,维护这样一个前缀和,就把\(O(nm^4)\)的程序优化到了\(O(nm^2)\),因为这两段分开枚举了。所以,当DP转移只需要用到上一阶段的状态而这一段不管,一般都可以用前缀和维护区间和/RMQ。

 

   不过提一下我犯的错误,就是对于②和③两部分,只关心了跨部分的转移而没有管自己的转移,实际上是需要的。不能粗心漏了这一点。

 

Code:

#include<cstdio>
#include<cstring>
int max(int x,int y)
{
    return x>y?x:y;
}
int f[210][210][210][3];
int b[210][210];//每行的前缀和
int g[210][210][3];//f数组的前缀和
int main()
{
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&b[i][j]);
            b[i][j]+=b[i][j-1];
        }
    for(int i=1;i<=n;i++)
    {
        //从大到小枚举r,从小到大枚举l,第二维的转移途径
        for(int r=m;r>=1;r--)
            for(int l=1;l<=r;l++)//g就是临时的前缀和数组
                g[l][r][0]=max(f[i-1][l][r][0],max(g[l][r+1][0],g[l-1][r][0]));
        for(int l=m;l>=1;l--)
            for(int r=l;r<=m;r++)
                g[l][r][1]=max(f[i-1][l][r][1],max(g[l][r-1][1],g[l+1][r][1]));
        //实际在这里转移过后,f的第一维就用不上了,可以压掉。
        for(int l=1;l<=m;l++)
            for(int r=l;r<=m;r++)
                if(b[i][r]-b[i][l-1]==0)//说明可以更新
                {
                    f[i][l][r][0]=f[i-1][l][r][0]+r-l+1;
                    if(g[l-1][r+1][0]!=0)
                        f[i][l][r][1]=g[l-1][r+1][0]+r-l+1;
                    if(f[i-1][l][r][1]>0)
                        f[i][l][r][1]=max(f[i][l][r][1],f[i-1][l][r][1]+r-l+1);
                    if(g[l+1][r-1][1]!=0)
                        f[i][l][r][2]=g[l+1][r-1][1]+r-l+1;
                    if(f[i-1][l][r][2]>0)
                        f[i][l][r][2]=max(f[i][l][r][2],f[i-1][l][r][2]+r-l+1);
                    ans=max(ans,f[i][l][r][2]);
                }
    }
    printf("%d",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */