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了
/* ***********************************************
Author :111qqz
Created Time :2016年08月03日 星期三 05时55分30秒
File Name :code/poj/1964.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <stack>
8#include <set>
9#include <map>
10#include <string>
11#include <cmath>
12#include <cstdlib>
13#include <ctime>
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E3+7;
7int n,m;
8char maze[N][N];
9int row[N][N],col[N][N];
10int a[N][N];
11int l[N][N],r[N][N];
12int main()
13{
14 #ifndef ONLINE_JUDGE
15 freopen("code/in.txt","r",stdin);
16 #endif
17 int T;
18 scanf("%d",&T);
19 while (T--)
20 {
21 ms(a,0);
22 scanf("%d%d",&n,&m);
23 getchar();
24 for ( int i = 1 ; i <= n ; i++)
25 {
26 for ( int j = 1 ; j <= m ; j++)
27 {
28 char ch = getchar();
29 while (ch!='F'&&ch!='R') ch = getchar();
30 maze[i][j]=ch;
31 }
32 maze[i][m+1] = 'R'; //单调栈的哨兵
33 }
34/* for ( int i = 1 ;i <= n ;i++){
35 for ( int j = 1 ; j <= m ; j++)
36 printf("%c ",maze[i][j]);
37 printf("\n");
38 } */
39 int x;
40 for ( int i = 1 ; i <= n ; i++)
41 {
42 stack<int>stk;
43 stk.push(m+1);
44 for ( int j = m ; j >=1 ; j--)
45 {
46 /* if (maze[i][j]=='R')
47 {
48 row[i][j]=j;
49 stk.push(j);
50 continue;
51 } */
52 for (x=stk.top() ; maze[i][x]=='F' ; x = stk.top()) stk.pop();
53 row[i][j] = x-1;
54 stk.push(j);
55 a[i][j] = row[i][j]-j+1;
56 if (maze[i][j]=='R') a[i][j] = 0 ;
57 }
58 }
59/* for ( int i = 1 ; i <= n ; i++)
60 {
61 for ( int j = 1 ; j <= m ; j++)
62 {
63 printf("%d ",a[i][j]);
64 }
65 printf("\n");
66 } */
67 for ( int j = 1 ; j <= m ; j++) //把a[i][j]看成高度，再做上下两个方向的单调栈
68 {
69 a[0][j]=a[n+1][j]=-1; //单调栈的哨兵
70 stack<int>stk;
71 stk.push(0);
72 for ( int i = 1 ; i <= n ; i++)
73 {
74 for (x=stk.top(); a[x][j]>=a[i][j] ; x = stk.top()) stk.pop();
75 l[i][j] = x+1;
76 stk.push(i);
77 }
78 while (!stk.empty()) stk.pop();
79 stk.push(n+1);
80 for ( int i = n ; i >=1 ; i --)
81 {
82 for (x = stk.top() ; a[x][j]>=a[i][j]; x = stk.top()) stk.pop();
83 r[i][j] = x-1;
84 stk.push(i);
85 }
86 }
87 int ans = 0 ;
88 for ( int i = 1 ; i <= n ; i++)
89 for ( int j = 1 ; j <= m ; j++)
90 if (maze[i][j]=='F')
91 ans = max(ans,(r[i][j]-l[i][j]+1)*a[i][j]);
92 printf("%d\n",ans*3);
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}