题解 P4147 【玉蟾宫】

Solution(单调栈做法) 请不要依靠名字颜色来臆断水平，谢谢！ 1.我们按行去划分，O(n)枚举行，对该行即以上的部分做最大矩阵处理； 2.那么我们用pos数组记录每行向上可延伸的最大距离，预处理的方式即为： (1)读到一个‘F’，该处pos=上一行该列pos的值+1； (2)读到一个‘R’，该处pos=0（因为该处不可向上伸展）； ``` memset(pos,0,sizeof(pos)); for(i=1;i<=n;++i) for(j=1;j<=m;++j){ x=getc(); if(x=='F')pos[i][j]=pos[i-1][j]+1; } ``` 3.那么对于每次枚举:对该行及以上的部分从左往右或从右往左进行一次单增栈，每次弹栈时更新最大面积; (1)栈内每个单位存入两个元素：该单位高度height和对应可控宽度length，对于每个大于栈顶直接入栈的元素，stack[i].length=1； (2)对于需要先弹栈再入栈的元素，其length=弹栈所有元素length之和+1，因为被弹栈的元素的高度均≥当前元素，所以其可控范围应加上被其弹栈元素的length； (3)在弹栈过程中，记录一个temp为本次弹栈到当前为止弹出的宽度，因为为单增栈，所以每个高度均可控其后被弹栈元素的宽度，所以其对应的面积为s=temp*h[i]，取max更新该行的maxs； 4.对每次枚举的maxs取max即为最终答案； ``` include<iostream> include<cstdio> include<cmath> include<cstring> include<algorithm> using namespace std; struct node{ int height,length; }stack[1010]; int n,m,i,j,k,pos[1010][1010],ans=0,maxs=0; char x; inline int read(){ int x=0; bool f=true; char c; c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=false; c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return f?x:-x; } char getc() { char c=getchar(); while(c!='R'&&c!='F')c=getchar(); return c; } void calc(int x){ int top=1,temp=0; maxs=0; stack[1].height=pos[x][1]; stack[1].length=1; for(i=2;i<=m;++i){ temp=0; while(stack[top].height>=pos[x][i]&&top>0){ temp+=stack[top].length; maxs=max(maxs,stack[top--].height*temp); } stack[++top].height=pos[x][i]; stack[top].length=temp+1; } temp=0; while(top>0){ temp+=stack[top].length; maxs=max(maxs,stack[top--].height*temp); } ans=max(ans,maxs); } int main(){ memset(pos,0,sizeof(pos)); n=read(); m=read(); for(i=1;i<=n;++i) for(j=1;j<=m;++j){ x=getc(); if(x=='F')pos[i][j]=pos[i-1][j]+1; } for(k=1;k<=n;++k) calc(k); ans*=3; printf("%lld\n",ans); return 0; } ``` 关于单调栈可以参考我的博客：http://www.cnblogs.com/COLIN-LIGHTNING/p/8474668.html 有什么问题欢迎各位大佬指出