hello.

题解 P4147 【玉蟾宫】

2018-01-23 22:17:33


思路

很容易发现,这是最大子矩形问题的板子题。

对于该类问题,王知昆dalao早已撰写过一篇论文讨论了通用的解决方案,我们可以阅读这篇论文:浅谈用极大化思想解决最大子矩形问题

对于这道题,由于障碍点密集,我们使用悬线法解决。//障碍点:在选取子矩形时不允许包含的点,本题中为“R”。

代码解释

设$h(i,j)$表示以$(i,j)$为下端点的悬线的最长长度。预处理$l(i,j)$和$r(i,j)$,它们分别表示点(i,j)能扩展到的左边和右边的最近的障碍。

$L(i,j)$和$R(i,j)$分别表示使悬线有此长度的左边最近的障碍和右边最近的障碍。

答案即为$max(h(i,j)*(R(i,j)-L(i,j)+1)$。

对于本题,要求输出答案乘3后的值。

C++代码

#include<bits/stdc++.h>  
using namespace std;  
const int maxn=1e3+10;  
int a[maxn][maxn],n,m,h[maxn][maxn],ans,t;char c;  
int l[maxn][maxn],r[maxn][maxn],L[maxn][maxn],R[maxn][maxn];  
int main(){ 
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)  
    for(int j=1;j<=m;j++)
    {cin>>c;if(c=='F') a[i][j]=1;} 
    for(int i=1;i<=n;i++){
        t=0;
        for(int j=1;j<=m;j++)//枚举左边的障碍
            if(a[i][j])l[i][j]=t;
            else L[i][j]=0,t=j;
        t=m+1;
        for(int j=m;j>=1;j--)//枚举右边的障碍
            if(a[i][j])r[i][j]=t;  
            else R[i][j]=m+1,t=j;      
    }
    for(int i=1;i<=m+1;i++) R[0][i]=m+1;
    for(int i=1;i<=n;i++)  
    for(int j=1;j<=m;j++){
        if(a[i][j]){
            h[i][j]=h[i-1][j]+1;//如果这个点是合法的,对应的悬线长度应当比它下面的点对应的悬线长大1  
            L[i][j]=max(l[i][j]+1, L[i-1][j]);
            R[i][j]=min(r[i][j]-1, R[i-1][j]);
            ans=max((R[i][j]-L[i][j]+1)*h[i][j], ans); //求出最大的面积          
        }
    }
    cout<<3*ans<<endl;
    return 0;
}