题目
有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
这片土地被分成 个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 ，它们将给你 两银子。
输入格式
第一行包括两个整数 ，表示矩形土地有 行 列。
接下来 行，每行 个用空格隔开的字符 F 或 R，描述了矩形土地。
每行末尾没有多余空格。
输出格式
输出一个整数，表示你能得到多少银子，即(最大 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
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int h[N][N], l[N], r[N], q[N];
char g[N][N];
int n, m;
int work(int a[])
{
a[0] = a[m + 1] = -1;
int tt = 0;
q[0] = 0;
for (int i = 1; i <= m; ++ i)
{
while (a[q[tt]] >= a[i]) -- tt;
l[i] = q[tt];
q[++ tt] = i;
}
tt = 0;
q[0] = m + 1;
for (int i = m; i; -- i)
{
while (a[q[tt]] >= a[i]) -- tt;
r[i] = q[tt];
q[++ tt] = i;
}
int res = 0;
for (int i = 1; i <= m; ++ i)
res = max(res, (r[i] - l[i] - 1) * a[i]);
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
{
char c;
cin >> c;
g[i][j] = c;
if (c == 'F') h[i][j] = h[i - 1][j] + 1;
else h[i][j] = 0;
}
int res = 0;
for (int i = 1; i <= n; ++ i)
res = max(res, work(h[i]));
cout << res * 3 << endl;
return 0;
}
|
