洛谷4147：玉蟾宫——题解-白红宇

洛谷4147：玉蟾宫——题解

阅读量：6177 次

发布时间：2019-06-21

本文共 1270 字，大约阅读时间需要 4 分钟。

土地被分成N*M个格子，每个格子里写着'R'或者'F'，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。

现在freda要找一块矩形土地，要求这片土地都标着'F'并且面积最大。

输出最大面积*3。

请食用王知昆论文：，和洛谷第一篇题解。

代码参自洛谷第一篇题解，然而那篇题解多了两个无用数组。

这里使用的是算法2（也叫悬线法）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=1010;inline char getc(){ char ch=getchar(); while(ch!='R'&&ch!='F')ch=getchar(); return ch;}int n,m,ans,mp[N][N],h[N][N],l[N][N],r[N][N];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ char ch=getc(); mp[i][j]=(ch=='F'); } } for(int i=1;i<=n;i++){ int t=0; for(int j=1;j<=m;j++){ if(mp[i][j])l[i][j]=t; else l[i][j]=0,t=j; } t=m+1; for(int j=m;j>=1;j--){ if(mp[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(mp[i][j]){ h[i][j]=h[i-1][j]+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(ans,(r[i][j]-l[i][j]+1)*h[i][j]); } } } printf("%d\n",3*ans); return 0;}