题目描述
这片土地被分成N*M个格子，每个格子里写着'R'或者'F'，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着'F'并且面积最大。
但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们每人给你S两银子。
输入输出格式
输入格式：
第一行两个整数N,M，表示矩形土地有N行M列。
接下来N行，每行M个用空格隔开的字符'F'或'R'，描述了矩形土地。
输出格式：
输出一个整数，表示你能得到多少银子，即(3*最大'F'矩形土地面积)的值。
输入输出样例
输入样例#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：
45
(Solution:)
一道傻不拉几的求最大矩形面积题qwq
首先处理一个 p 数组，表示向上可拓展多少高度，是 “ F ” 就从上面那个转移过来，是 “ R ” 就等于 0 。然后枚举每一行，对于每一行求一个最大矩形面积
重点来了，怎么求最大矩形面积？请听下回分解
开一个栈，用来记录单调上升的矩阵，接下来的矩阵如果高度大于 top ，就加进去；如果小于，就把栈弹到大于为止，即把栈中高于当前矩阵的矩阵弹掉并处理一下，并且每一次弹栈时都记录一下答案。
如果有这么一个图：
首先一直加，不需要记录答案，直到第5个矩阵：
那么就把第3,4号矩阵弹掉，并相应地把2号矩阵的宽度改掉，即改成这种样子：
在过程中开一个指针leng，表示你弹掉的矩阵的总长度，在每弹一个时计算一下答案：(leng * l[top].hi) 。比如弹第三个时：
此时 leng=2 ，(l[top].hi) 为第三个矩阵的高度，计算的是蓝色区域的面积。
最后把第4号的宽度也加进去，所以栈中有两个元素，第一号宽度为 1 ，第二个为 4 。
跑完时一定要记得把栈清空，弹栈的程序一样，也要计算答案。
具体请配合代码食用：
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int f=1,w=0;char c=0;
while(!isdigit(c))
{
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) w=w*10+(c^48),c=getchar();
return f*w;
}
struct line{
int le,hi;
}l[1010];//栈
int T,n,m,p[1010][1010],s[1010],ans;
int check(int q){
int tp=1,res=p[q][1];
l[1].hi=res,l[1].le=1;
for(int i=2;i<=m;i++)
{
if(p[q][i]>=l[tp].hi)
{
l[++tp].le=1;
l[tp].hi=p[q][i];
}//高度大于，直接加栈
else
{
int leng=0;
while(l[tp].hi>p[q][i])
{
leng+=l[tp].le;
res=max(res,leng*l[tp].hi);//弹的时候记录一下答案
tp--;
}
l[++tp].le=leng+1;
l[tp].hi=p[q][i];//入栈
}
}
int leng=0;
while(tp)
{
leng+=l[tp].le;
res=max(res,leng*l[tp].hi);
tp--;
}//弹栈并计算
return res;
}
int main(){
ans=0;
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char c;cin>>c;
if(c=='F') p[i][j]=p[i-1][j]+1;
else p[i][j]=0;
}//预处理P数组
for(int i=1;i<=n;i++)//枚举行号
ans=max(ans,check(i));
printf("%d
",ans*3);
return 0;
}
就酱qwq