题解 P4147 【玉蟾宫】
XG_Zepto
2018-01-23 22:17:33
## 思路
很容易发现，这是**最大子矩形问题**的板子题。
对于该类问题，王知昆dalao早已撰写过一篇论文讨论了通用的解决方案，我们可以阅读这篇论文：[浅谈用极大化思想解决最大子矩形问题](http://blog.csdn.net/twtsa/article/details/8120269)。
对于这道题，由于障碍点密集，我们使用**悬线法**解决。//障碍点：在选取子矩形时不允许包含的点，本题中为“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++代码
```cpp
#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;
}
```