★   输入文件：jademoon.in   输出文件：jademoon.out   简单对比

时间限制：1 s   内存限制：128 MB

【背景】

有一天，小猫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 6R F F F F FF F F F F FR R R F F FF F F F F FF 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)。

代码实现

1 #include
     
       2 const int maxn=1e3+10; 3 inline int max_(int x,int y){
   return x>y?x:y;} 4 int n,m,ans; 5 int map[maxn][maxn]; 6 char ch[3]; 7 int q[maxn],s[maxn],top; 8 void do_stack(int k){ 9     q[top=1]=map[k][1],s[top]=1;10     for(int i=2;i<=m+1;i++){11         int j=0;12         while(map[k][i]