【背景】

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

【题目描述】

这片土地被分成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'矩形土地面积)的值。

【样例输入】

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 
 

【样例输出】

45

【提示】

各个测试点1s

对于50%的数据，1<=N,M<=200
对于100%的数据，1<=N,M<=1000

题解：

本题是一个练习单调堆栈的题，也是本人第一次写单调堆栈，在某天的晚上看完官方题解，想着想着睡着了。。。（当时认为官方题解有问题），后来在第二天早上买饭去机房的路上顿悟。。。其实不难，呵呵。先上官方题解，如若看懂则不必要往后看。

官方题解：

们先来考虑这样一个问题，水平线上有一些宽度为1，高度不定的阴影区域，要求找到包含在这个区域内的一个矩形，使得矩形面积最大。

如图所示，高度不一的柱形条就是阴影区域，不同颜色框出的矩形都满足要求，其中红色矩形的面积最大。

维护一个栈中元素高度单调递增的栈，初始化栈中第一个元素高度宽度均为0。

然后每次读入一个矩形，若它比栈顶元素还高就直接进栈；

否则不断将栈中元素弹栈，直到当前栈顶元素能够与读入的矩形满足高度递增。

弹栈过程中累加弹出的元素的宽度，然后每弹出一个就判断（当前弹出元素的高度×累加的宽度）能否更新最大面积ans。

然后以新的矩形高度作高，刚才弹出栈的元素总宽度加上新矩形宽度作宽，把这个矩形插入到栈里。

最终栈肯定是一个单调的，只需要再把栈一个个弹空，弹栈过程中仍像上面那样计算即可。

这个算法的时间复杂度是O(n)的。

在本题中，我们只需要枚举每一行以上的'F'作为阴影区域，用上述单调栈算法求一遍最大矩形面积即可。时间复杂度O(NM)。

 说实话，鄙人的理解能力不是很强，看完后基本上一点都不懂。。。后来想想，其实就是将这个矩阵变成了N个矩阵。（一每一行为底边的矩阵），在按照上面的思路做。

 在我的程序里，w[i][j]表示第j列向上的i个土地中连续为F的个数。这就相当于一个个矩形，每一行都有j个矩形，这样枚举每一行，按照官方的方法一遍一遍找就行了。

源程序：

C++语言: 

made by PaulInsider!
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,m,w[1005][1005]={0},answer=0;
char a;
int q[1005]={0},num,weight,high,t[1005];
int main()
{
   freopen ("jademoon.in","r",stdin);
   freopen ("jademoon.out","w",stdout);
   cin>>n>>m;
   for (int o=1;o<=n;o++)
   {
       for (int p=1;p<=m;p++)
       {
           cin>>a;
           if (a=='R')
               continue;
           w[o][p]=w[o-1][p]+1;
       }
   }
   for (int i=1;i<=n;i++)
   {
       memset(q,0,sizeof(q));
       q[0]=-1;num=0;
       memset(t,0,sizeof(t));
       for (int j=1;j<=m;j++)
       {
           weight=0;high=w[i][j];
           while (high<q[num])
           {
               weight+=t[num];
               if (weight*q[num]>answer)
                   answer=weight*q[num];
               num--;
           }
           num++;
           q[num]=high;
           t[num]=weight+1;
       }
       weight=0;
       while (num)
       {
           weight+=t[num];
           if (weight*q[num]>answer)
               answer=weight*q[num];
           num--;
       }
   }
   cout<<3*answer;
   return 0;
}