题解 P4147 【玉蟾宫】

蒟蒻只会用**悬线法**。 ------------ 悬线法思路：悬线的定义，就是一条竖线，这条竖线要满足上端点在整个矩形上边界或者是一个障碍点。然后以这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进而确定这条悬线所在的极大矩阵。 ------------ 具体方法： 先预处理： 用数组l，r记录某点向左和向右能到达的最远点的纵坐标。 用数组up记录某点向上能到达的最远距离。 ``` //处理l for(i=1;i<=n;i++) for(j=2;j<=m;j++) if(map[i][j]==1&&map[i][j-1]==1) l[i][j]=l[i][j-1]; //处理r for(i=1;i<=n;i++) for(j=m-1;j>0;j--) if(map[i][j]==1&&map[i][j+1]==1) r[i][j]=r[i][j+1]; ``` 然后只需对每个点都找一遍矩形的最大面积 ``` for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(i>1&&map[i][j]==1&&map[i-1][j]==1){ r[i][j]=min(r[i][j],r[i-1][j]); l[i][j]=max(l[i][j],l[i-1][j]); up[i][j]=up[i-1][j]+1; } ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]); } } ``` **记得输出时要乘3** 完整AC代码 ``` #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; inline int Read(){ int x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}; while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*f; }//读入优化 inline int Readc(){ char c=getchar(); while(c!='R'&&c!='F')c=getchar(); if(c=='F')return 1; return 0; }//F能用，E不能用 inline int max(int x,int y){ return x>y?x:y; } inline int min(int x,int y){ return x<y?x:y; } //max和min最好自己打 int n,m,ans1,ans,map[1001][1001];; //ans：最大矩形;map[i][j]：(i,j)的值 ，0不能用，1可以用 int l[2018][2018],r[2018][2018]; //l[i][j],r[i][j],up[i][j]分别表示(i,j)左，右能到达的最远的点的纵坐标 int up[2018][2018]; //向上到达最远的点的距离 int main(){ register int i,j; ans=0; n=Read(),m=Read(); for(i=1;i<=n;i++) for(j=1;j<=m;j++) map[i][j]=Readc(),up[i][j]=1,r[i][j]=l[i][j]=j; //处理l for(i=1;i<=n;i++) for(j=2;j<=m;j++) if(map[i][j]==1&&map[i][j-1]==1) l[i][j]=l[i][j-1]; //处理r for(i=1;i<=n;i++) for(j=m-1;j>0;j--) if(map[i][j]==1&&map[i][j+1]==1) r[i][j]=r[i][j+1]; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(i>1&&map[i][j]==1&&map[i-1][j]==1){ r[i][j]=min(r[i][j],r[i-1][j]); l[i][j]=max(l[i][j],l[i-1][j]); up[i][j]=up[i-1][j]+1; } ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]); } } printf("%d",3*ans); return 0; } ``` ~~**求赞**~~