题解 P4147 【玉蟾宫】

· · 题解

新学的悬线法。。

本题的题意就是，在一个有障碍的矩形中寻找一个最大的不包含障碍的矩形。

直接枚举四条边界判断合法肯定是不行的，这样做起码是O(n^5)的复杂度。 悬线法运用了贪心的思想，那就是对于每一个点，考虑他以某种方式所能形成的一个极大的矩形。

显然，一个极大矩形应该是上下左右都不能再向外扩充的矩形。

悬线法利用了这个结论，考虑的是以每一个障碍物或上边界为上边界的极大矩形。

如图所示，1号矩形的上边界是本题的上边界，2号矩形的上边界由向上方走遇到的第一个障碍决定，3号矩形也是如此。

可以枚举下边界上的一个点来确定这个矩形的最大高度，也就是图中的1️⃣2️⃣3️⃣。当这个点向上没有碰到障碍或边界时矩形高度+1。高度确定了之后就可以由中间的行确定他的宽度。

对于每一个点，我们记录ta向上、向左、向右最多能扩充的长度。每个点所生成的极大矩形由包含它的最高的矩形决定【事实上和单调栈的思路有点类似】。

为什么这样能枚举到所有的极大矩形呢？

当枚举到1️⃣号点时，他对答案的贡献只有红色的矩形，但他其实同时也包含在绿色的矩形里面啊？

但是，很容易就会发现其实绿色的矩形在枚举2️⃣号点的时候就已经枚举到了。

这里极大矩形的高度和宽度是互相制约的，确定一个，再让另外一个尽量大就好了。

~~~~

代码部分，首先需要预处理出每个点向上向左向右的最长距离：

const int MAXN = 1017;
int n, m;
int G[MAXN][MAXN];
int up[MAXN][MAXN];
int l[MAXN][MAXN];
int r[MAXN][MAXN];

for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            if(!G[i][j]) continue;
            l[i][j] = l[i][j-1] + 1;
        }
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 1; j--){
            if(!G[i][j]) continue;
            r[i][j] = r[i][j+1] + 1;
        }

然后需要优先满足从本点向上最高的矩形所能达到的宽度：

for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i > 1 && G[i][j] && G[i-1][j]){
                up[i][j] = up[i-1][j] + 1;
                l[i][j] = min(l[i][j], l[i-1][j]);
                r[i][j] = min(r[i][j], r[i-1][j]);
            }
            maxs = max(maxs, (up[i][j] + 1) * (l[i][j] + r[i][j] - 1)); //高度应该+1，宽度应该-1，小细节要注意
        }
    }

AC代码

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1017;
int n, m;
int G[MAXN][MAXN];
int up[MAXN][MAXN];
int l[MAXN][MAXN];
int r[MAXN][MAXN];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            char ch;
            cin >> ch;
            if(ch == 'F')
                G[i][j] = 1;
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            if(!G[i][j]) continue;
            l[i][j] = l[i][j-1] + 1;
        }
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 1; j--){
            if(!G[i][j]) continue;
            r[i][j] = r[i][j+1] + 1;
        }
    int maxs = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i > 1 && G[i][j] && G[i-1][j]){
                up[i][j] = up[i-1][j] + 1;
                l[i][j] = min(l[i][j], l[i-1][j]);
                r[i][j] = min(r[i][j], r[i-1][j]);
            //printf("## (%d, %d) %d %d %d\n", i, j, l[i][j], r[i][j], up[i][j]);
            }
            maxs = max(maxs, (up[i][j] + 1) * (l[i][j] + r[i][j] - 1));
        }
    }
    cout << 3 * maxs << endl;
}