P4147 玉蟾宫

极简极短版速写
单调栈
这里要找每个柱 左侧 以及 右侧 第一个比当前柱短的柱子的位置：
构建一个从栈顶到栈底的单调递减栈，只有想要入栈的元素大于栈顶元素时，才能入栈，否则栈顶元素出栈。
从左到右遍历，
栈顶元素出栈时 表明 栈顶元素找到了右边第一个小于它的柱子（的位置）；而且此时栈内 栈顶元素的前一个元素 是 当前栈顶元素左侧第一个小于它的元素
这样某个元素的左右侧第一个小于它的元素都找到了
 
栈顶元素连续出栈？上述过程照常举行。
 
在一次出栈时即可找到第一个比当前数小的数的位置，以及最后一个比当前数小的数的位置。
一次入栈出栈就解决题目不用从另一个方向遍历第二次

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N=1005;
4. int Map[N][N],stk[N];
5. int n,m,top,ans;
6. char o;
7. int main()
8. {
9.     cin>>n>>m;
10.     for(int i=1;i<=n;i++){
11.         top=0;
12.         for(int j=1;j<=m+1;j++){
13.             if(j!=m+1){
14.                 cin>>o;
15.                 if(o=='F')Map[i][j]=Map[i-1][j]+1;
16.                 // else Map[i][j]=0;
17.             }
18.             while(top&&Map[i][stk[top]]>=Map[i][j]){
19.                 int h=Map[i][stk[top]];
20.                 top--;
21.                 int l=top?stk[top]:0;
22.                 ans=max(ans,(j-l-1)*h);
23.             }
24.             stk[++top]=j;
25.         }
26.     }
27.     cout<<3*ans;
28.     return 0;
29. }

复制代码

确实是我颠末反复碰钉子+看题解后两个月后自己写出来的。
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。