题目描述：
有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
题目描述
这片土地被分成 $N\times M$ 个格子，每个格子里写着 ‘R’ 或者 ‘F’，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 ‘F’ 并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 $S$ ，它们每人给你两 $S$ 银子。
输入格式
第一行两个整数 $N,M$ ，表示矩形土地有 $N\times M$ 列。
接下来 $N$ 行，每行 $M$ 个用空格隔开的字符 ‘F’ 或 ‘R’，描述了矩形土地。
输出格式
输出一个整数，表示你能得到多少银子，即 ( $3\times S$ ) 的值。
数据范围：
$1\le N,M\le 1000$
题解：
略，注意更新高度的时候，从 $i-1$ 更新过来。
代码：
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
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int matrix[maxn][maxn];
int l[maxn][maxn], r[maxn][maxn];
int h[maxn][maxn];
void solve()
{
int ans = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (matrix[i][j] == 1)
l[i][j] = l[i][j - 1] + 1;
}
for (int j = m; j >= 1; --j)
{
if (matrix[i][j] == 1)
r[i][j] = r[i][j + 1] + 1;
}
for (int j = 1; j <= m; ++j)
{
h[i][j] = matrix[i][j];
if (i >= 2 && matrix[i - 1][j] == 1)
{
l[i][j] = min(l[i][j], l[i - 1][j]);
r[i][j] = min(r[i][j], r[i - 1][j]);
h[i][j] = h[i - 1][j] + 1;
}
ans = max(ans, (l[i][j] + r[i][j] - 1) * h[i][j]);
}
}
cout << 3 * ans << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
char ch;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cin >> ch;
matrix[i][j] = (ch == 'F');
}
}
solve();
return 0;
}
|