P3135题解

xkcdjerry · 2021-08-23 11:34:35 · 题解

这道题很多人是拿 DP 做的，但是由于数据不是很强可以用 O(n^4) 的玄学暴力卡过去：

首先考虑最简单的 O(n^5) 做法： O(n^2) 枚举左上角，O(n) 枚举长， O(n) 枚举宽，O(n) 验证，共计 O(n^5)。
由于验证只是求四条边是否全是 . ，即四条边是否 . 的个数等于长度，可以使用前缀和优化做到 O(n^4) 。

但是如果代码这么写就会获得 78 分的好成绩，考虑优化：

可以令 x,y 逆序循环，i,j 正序循环，那么显然每一层循环每跑一次可能画出矩形的最大值就会更小，因此：

• 如果 y 循环内找到了可行解可以直接跳出，因为后面一定找不到更大的了。
• 在任何一层循环里如果能够取到的最大值 \leqslant mx 也可以跳出，原因同上。

加上优化之后的代码可以取得 93 分，而且还有一个大的优化点：

观察代码可以发现 col[x][j]-col[i-1][j]==x-i+1 与 y 无关。可以提取到 x 循环中。减少求值和提前剪裁掉不符合的答案。

这个优化后代码终于获得了 100 分，不开 O2 时时间为 77ms，开了之后为 54ms，是当前（2021 年 8 月 25 日）的最优解。

完整代码如下：

#include <cstdio>
#define N 210
int n,m;
int a[N][N];
int row[N][N],col[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        char c;
        scanf(" %c",&c);
        a[i][j]=c=='.';
        row[i][j]=row[i][j-1]+a[i][j];
        col[i][j]=col[i-1][j]+a[i][j];
    }
    int mx=-1;
    for(int i=1;i<=n;i++)
    {
        if((n-i+1)*m<=mx) break;
        for(int j=1;j<=m;j++)
        {
            if((n-i+1)*(m-j+1)<=mx) break;
            for(int x=n;x>=i;x--)
            {
                if((x-i+1)*(m-j+1)<=mx) break;
                if(col[x][j]-col[i-1][j]!=x-i+1) continue;//左
                for(int y=m;y>=j;y--)
                {
                    if((x-i+1)*(y-j+1)<=mx) break;
                    if(row[i][y]-row[i][j-1]==y-j+1&& //上
                            row[x][y]-row[x][j-1]==y-j+1&& //下
                            col[x][y]-col[i-1][y]==x-i+1) //右
                    {
                        mx=(x-i+1)*(y-j+1);
                        break;
                    }
                }
            }
        }
    }
    printf("%d",mx);
    return 0;
}