有一天,小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。
这片土地被分成 N×M 个格子,每个格子里写着 R 或者 F,R 代表这块土地被赐予了 rainbow,F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着 F 并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了,找不出这块土地,而蓝兔也想看 freda 卖萌(她显然是不会编程的……),所以它们决定,如果你找到的土地面积为 S,它们将给你 3×S 两银子。
输入格式
第一行包括两个整数 N,M,表示矩形土地有 N 行 M 列。
接下来 N 行,每行 M 个用空格隔开的字符 F 或 R,描述了矩形土地。
每行末尾没有多余空格。
输出格式
输出一个整数,表示你能得到多少银子,即(3×最大 F 矩形土地面积)的值。
数据范围
1≤N,M≤1000
输入样例:
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
进阶题目 3516:最大面积
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int h[N][N], q[N], l[N], r[N], tt;
// 将问题抽象成在第1 ~ n行中,在第 i 行中每一列 F 最高有多高,即问题转化为 131 题目中直方图的最大矩形面积问题
int main()
{
cin >> n >> m;
//预处理一下第 i 行上 F 有多高
for (int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
{
char x;
cin >> x;
if(x == 'F') h[i][j] = h[i - 1][j] + 1;
}
int res = 0;
for(int i = 1; i <= n; i ++ )
{
h[i][0] = h[i][m + 1] = -1; // 处理边界,不用写 tt > 0
//从左往右处理l的单调队列
tt = 0, q[0] = 0;
for(int j = 1; j <= m; j ++ )
{
while(h[i][q[tt]] >= h[i][j]) tt -- ;
l[j] = q[tt];
q[ ++ tt] = j;
}
//从右往左处理r
tt = 0, q[0] = m + 1;
for(int j = m; j; j -- )
{
while(h[i][q[tt]] >= h[i][j]) tt -- ;
r[j] = q[tt];
q[ ++ tt ] = j;
}
//从左往右依次枚举每次最大的矩形面积
for(int j = 1; j <= m; j ++ )
res = max(res, h[i][j] * (r[j] - l[j] - 1));
}
cout << res * 3 << endl;
return 0;
}