poj 1964 City Game(单调栈，输入挂)
题意：n*m的maze,由’R’和‘F’组成，现在要求找到面积最大的矩形，使得矩形中所有格子都是’F’。
思路：单调栈…一开始神tm tle….复杂度没问题啊。。。
结果看到有人说这题由于数据量比较大。。。scanf会超时。。。所以要用输入挂。。。。。getchar什么的。。。
poj竟然也卡读入。。。人性呢。。。。
改了输出以后再交wa了。
发现想错了，我是写了从(i,j)到两个方向能到的最大距离。。但是这样写有些点上的情况是没有考虑到的。。比如如果(i+1,j+1)上的点是’R’，实际上是不可以构成l*r的矩形的(l>=2&r>=2)。。。但是我这样做无法体现。
改了下，变成：
仍然对于每行做一次单调栈，预处理出点(i,j)能往右的最远距离a[i][j]。
然后观察一下。。。如果我把每一列分别看成x轴，那a[i][j]不就是矩形的高度了吗。。。
那我要求的不又变成了最大矩形面积了吗。。。
于是接下来对于每一列，做上下两个方向的单调栈得到（i,j）上下能延伸到的最远距离。
(i,j)点所在的矩形面积就是** (r[i][j]-l[i][j]+1)a[i][j];*
再交，A了
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月03日 星期三 05时55分30秒
4File Name :code/poj/1964.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E3+7;
35int n,m;
36char maze[N][N];
37int row[N][N],col[N][N];
38int a[N][N];
39int l[N][N],r[N][N];
40int main()
41{
42 #ifndef ONLINE_JUDGE
43 freopen("code/in.txt","r",stdin);
44 #endif
45 int T;
46 scanf("%d",&T);
47 while (T--)
48 {
49 ms(a,0);
50 scanf("%d%d",&n,&m);
51 getchar();
52 for ( int i = 1 ; i <= n ; i++)
53 {
54 for ( int j = 1 ; j <= m ; j++)
55 {
56 char ch = getchar();
57 while (ch!='F'&&ch!='R') ch = getchar();
58 maze[i][j]=ch;
59 }
60 maze[i][m+1] = 'R'; //单调栈的哨兵
61 }
62/* for ( int i = 1 ;i <= n ;i++){
63 for ( int j = 1 ; j <= m ; j++)
64 printf("%c ",maze[i][j]);
65 printf("\n");
66 } */
67 int x;
68 for ( int i = 1 ; i <= n ; i++)
69 {
70 stack<int>stk;
71 stk.push(m+1);
72 for ( int j = m ; j >=1 ; j--)
73 {
74 /* if (maze[i][j]=='R')
75 {
76 row[i][j]=j;
77 stk.push(j);
78 continue;
79 } */
80 for (x=stk.top() ; maze[i][x]=='F' ; x = stk.top()) stk.pop();
81 row[i][j] = x-1;
82 stk.push(j);
83 a[i][j] = row[i][j]-j+1;
84 if (maze[i][j]=='R') a[i][j] = 0 ;
85 }
86 }
87/* for ( int i = 1 ; i <= n ; i++)
88 {
89 for ( int j = 1 ; j <= m ; j++)
90 {
91 printf("%d ",a[i][j]);
92 }
93 printf("\n");
94 } */
95 for ( int j = 1 ; j <= m ; j++) //把a[i][j]看成高度，再做上下两个方向的单调栈
96 {
97 a[0][j]=a[n+1][j]=-1; //单调栈的哨兵
98 stack<int>stk;
99 stk.push(0);
100 for ( int i = 1 ; i <= n ; i++)
101 {
102 for (x=stk.top(); a[x][j]>=a[i][j] ; x = stk.top()) stk.pop();
103 l[i][j] = x+1;
104 stk.push(i);
105 }
106 while (!stk.empty()) stk.pop();
107 stk.push(n+1);
108 for ( int i = n ; i >=1 ; i --)
109 {
110 for (x = stk.top() ; a[x][j]>=a[i][j]; x = stk.top()) stk.pop();
111 r[i][j] = x-1;
112 stk.push(i);
113 }
114 }
115 int ans = 0 ;
116 for ( int i = 1 ; i <= n ; i++)
117 for ( int j = 1 ; j <= m ; j++)
118 if (maze[i][j]=='F')
119 ans = max(ans,(r[i][j]-l[i][j]+1)*a[i][j]);
120 printf("%d\n",ans*3);
121
122
123 }
124
125 #ifndef ONLINE_JUDGE
126 fclose(stdin);
127 #endif
128 return 0;
129}