P4147 玉蟾宫(悬线法求最大子矩阵)

时间:2021-07-15 02:36:53

P4147 玉蟾宫

悬线法 ,\(l_{i,j},r_{i,j},up_{i,j}\) 分别表示 \((i,j)\) 这个点向左,右,上能到达的远点。然后面积就很好办了。具体实现见代码。

然而,还有更优秀的算法,可是我还没学会嘤嘤嘤,可以看看这题:P1578 奶牛浴场

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N],l[N][N],r[N][N],n,m,mp[N][N],ans;
int rd()
{
#define gc() getchar()
char c=gc();
while(c!='R'&&c!='F')c=gc();
return c=='F'?1:0;
}
int max(const int &a,const int &b){return a>b?a:b;}
int min(const int &a,const int &b){return a<b?a:b;}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
mp[i][j]=rd(),l[i][j]=r[i][j]=j,a[i][j]=1;
for(int i=1;i<=n;++i)
for(int j=2;j<=m;++j)
if(mp[i][j]&&mp[i][j-1])
l[i][j]=l[i][j-1];
for(int i=1;i<=n;++i)
for(int j=m-1;j>=1;--j)
if(mp[i][j]&&mp[i][j+1])
r[i][j]=r[i][j+1];
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(i>1&&mp[i][j]&&mp[i-1][j])
{
a[i][j]=a[i-1][j]+1;
l[i][j]=max(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
}
ans=max(ans,(r[i][j]-l[i][j]+1)*a[i][j]);
}
}
printf("%d\n",ans*3);
return 0;
}