bzoj 3039 玉蟾宫

xiaoxiao2023-03-27  28

链接

算法:暴力

题解:

悬线法求最大全0子矩形模板题。  h(i,j)表示点(i,j)悬线的最长长度,l(i,j)和r(i,j)分别表示点(i,j)的悬线能到h(i,j)这个长度的左右端点的限制。  预处理L(i,j)R(i,j)表示距点(i,j)左边和右边最近的障碍。  那么如果(i,j)为障碍点的话,h(i,j)=0,l(i,j)=0,r(i,j)=m+1;  如果(i,j)不是障碍点的话,h(i,j)=h(i-1,j)+1,l(i,j)=max(l(i-1,j),L(i,j)),r(i,j)=min(r(i-1,j),R(i,j));  最终的答案为3*max{h(i,j)*(r(i,j)-l(i,j)-1)}  

代码如下:

#include<iostream> #include<cstdio> #define N 1005 using namespace std; char mapp[N][N]; int l[N],r[N],h[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { scanf("%s",&mapp[i][j]); } } for(int i = 1;i <= n;i++) { l[i]=1,r[i]=m;//初始化 } int ans=0; for(int i = 1;i <= n;i++) { int left=0,right=m+1;// left记录当前点向左可以延伸到的位置,right记录当前点向右可以延伸到的位置。 for(int j = 1;j <= m;j++) { if(mapp[i][j]=='F') { h[j]++;//更新当前点高度 l[j]=max(l[j],left+1); }else { h[j]=0;//该点往下高度从新计算 left=j; l[j]=1; } } for(int j = m;j >= 1;j--)//类比left,但是高度不必再重复计算!!!! { if(mapp[i][j]=='F') { r[j]=min(r[j],right-1); }else { right=j; r[j]=m; } ans=max(ans,(r[j]-l[j]+1)*h[j]);//计算面积 } } printf("%d",ans*3); return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-4988247.html

最新回复(0)