P4147 玉蟾宫

题目背景

有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

题目描述

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

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

但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的最大的土地面积为 $S$，它们每人给你 $S$ 两银子。

输入格式

第一行两个整数 $N$，$M$，表示矩形土地有 $N$ 行 $M$ 列。

接下来 $N$ 行，每行 $M$ 个用空格隔开的字符 F 或 R，描述了矩形土地。

输出格式

输出一个整数，表示你能得到多少银子，即 $3\times S$ 的值。

输入输出样例 #1

输入 #1

5 6 
R F F F F F 
F F F F F F 
R R R F F F 
F F F F F F 
F F F F F F

输出 #1

说明/提示

对于 $50\%$ 的数据，$1 \leq N, M \leq 200$。
对于 $100\%$ 的数据，$1 \leq N, M \leq 1000$。

第一次学习的时候是使用的悬线法，也就是往下拉一条线得到一个高度，然后计算在这个高度上被左右边界约束的最大宽，然后直接宽*高得到结果；具体过程是准备三个二维数组，分别命名为h：当前位置到顶上的高，l：当前位置的最大左边界，r：当前位置的最大右边界。然后只要暴力就行，写一个双层的循环，先更新当前位置的高，也就是如果这个位置没有被占据,当前位置的高度就是头上的+1，也就是h_ij=h_{i-1 j} +1;然后对于每一行来说，只要正反各扫一遍就可以得到当前位置的左右边界
最后暴力枚举一遍所有点，并且维护约束边界，计算答案就可以了

cpp void Refra1n() { ll n,m;cin>>n>>m; vector<vector<char>>a(n+1,vector<char>(m+1)); vector<vector<ll>>h(n+1,vector<ll>(m+1)),l(n+1,vector<ll>(m+1)),r(n+1,vector<ll>(m+1)); ll cntr=0; for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ cin>>a[i][j]; if(a[i][j]=='R')cntr++; h[i][j]=1;l[i][j]=r[i][j]=j;//读入和初始化 } for(ll j=2;j<=m;j++){//正向扫一遍得到当前的左边界 if(a[i][j]=='F'&&a[i][j-1]=='F') l[i][j]=l[i][j-1]; } for(ll j=m-1;j>=1;j--){//反向扫一遍得到当前的右边界 if(a[i][j]=='F'&&a[i][j+1]=='F'){ r[i][j]=r[i][j+1]; } } } if(cntr==n*m){//如果没有空地，因为初始化为1，所以要注意 cout<<0<<endl; return; } ll ans=0; for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ if(i>1&&a[i][j]=='F'){ if(a[i-1][j]=='F'){ h[i][j]=h[i-1][j]+1;//维护高度约束 l[i][j]=max(l[i][j],l[i-1][j]);//维护左边界约束 r[i][j]=min(r[i][j],r[i-1][j]);//维护右边界约束 } } ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);//计算得到结果 } } cout<<ans*3<<endl; }我们很容易发现这个写法对于空间消耗是特别大的，所以可以用滚动数组技巧解决，但是滚动数组不便于维护当前约束值，此时我们想到单调栈，在正式使用单调栈写P4147前，先引入单调栈的概念吧！

P2866 [USACO06NOV] Bad Hair Day S

题目描述

农夫约翰有 $N$ 头奶牛正在过乱头发节。

每一头牛都站在同一排面朝右，它们被从左到右依次编号为 $1, 2, \cdots, N$。编号为 $i$ 的牛身高为 $h_i$。第 $N$ 头牛在最前面，而第 $1$ 头牛在最后面。

对于第 $i$ 头牛前面的第 $j$ 头牛，如果 $h_i>h_{i+1}, h_i>h_{i+2}, \cdots, h_i>h_j$，那么认为第 $i$ 头牛可以看到第 $i+1$ 到第 $j$ 头牛。

定义 $C_i$ 为第 $i$ 头牛所能看到的牛的数量。请帮助农夫约翰求出 $C _ 1 + C _ 2 + \cdots + C _ N$。

输入格式

输入共 $N + 1$ 行。

第一行为一个整数 $N$，代表牛的个数。
接下来 $N$ 行，每行一个整数 $a _ i$，分别代表第 $1, 2, \cdots, N$ 头牛的身高。

输出格式

输出共一行一个整数，代表 $C _ 1 + C _ 2 + \cdots + C _ N$。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq N \leq 8 \times 10 ^ 4$，$1 \leq h _ i \leq 10 ^ 9$。

正向枚举的时间复杂度是O(n²),我们反向考虑问题就好了，也就是从“一个奶牛右边有几个比他矮”转化为“一个奶牛左边有几头奶牛比他高”，可以证明，最后的和是一样的；
而单调栈正是维护一个单调递增/递减的数据结构，以递增栈为例：其过程就是逐个将数据入栈，如果当前数据小于栈顶数据，则弹出栈顶数据，直到栈为空或者当前数据小于栈顶数据，再将当前元素推入栈，代码如下；

cpp while(x<a.back()&&a.size()){//当前元素为x a.pop_back(); } a.push_back(x);
对于本题只要改一下写法就行
cpp void Refra1n() { ll n,x,ans=0;cin>>n; vector<ll>a; for(ll i=0;i<n;i++){ cin>>x; while(a.back()<=x&&a.size()){ a.pop_back(); } a.push_back(x); ans+=a.size()-1; } cout<<ans<<endl; }接下来我们扩展到P4147
悬线依旧可以维护，但是对于每个位置的左右边界我们放到计算答案的循环里处理
也就是当前位置的高度更小的话，这个就是边界，如果对这部分有疑惑的话可以画图，这里的话其实就是一个直方图📊，然后高的地方边界肯定不能走到矮的地方，而矮的可以走到高的地方，也就是单调栈，整个问题就转变为枚举底边位置计算直方图中最大面积；代码如下
cpp void Refra1n() { ll m,n;cin>>n>>m; vector<vector<char>>a(n+1,vector<char>(m+1)); for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin>>a[i][j]; vector<ll>h(m+1),l(m+1),r(m+1); ll S=0; for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ h[j]= a[i][j]=='R'?0:h[j]+1;//如果没有障碍，则继承上方高度并且+1，否则此处高度为0 } vector<ll>st; for(ll j=1;j<=m;j++){ while(st.size()&&h[j]<h[st.back()]){ r[st.back()]=j; st.pop_back(); } st.push_back(j); } while(st.size()){//清空栈，并且将剩下元素的边界设置为地图的边界 r[st.back()]=m+1; st.pop_back(); } for(ll j=m;j>=1;j--){ while(st.size()&&h[j]<h[st.back()]){ l[st.back()]=j; st.pop_back(); } st.push_back(j); } while(st.size()){ l[st.back()]=0; st.pop_back(); } for(ll j=1;j<=m;j++){ if(S<h[j]*(r[j]-l[j]-1)){ S=h[j]*(r[j]-l[j]-1); } } } cout<<S*3<<endl; }
再推荐一道差不多的题目洛谷P1950
接下来就是喜闻乐见的打boss：洛谷P1578

P1578 [WC2002] 奶牛浴场

题目描述

由于 John 建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John 决定在牛场中建造一个大型浴场。但是 John 的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John 希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于 Clevow 了。你还能帮助 Clevow 吗？

John 的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。

Clevow 当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。