题目描述
有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。
这片土地被分成N*M个格子,每个格子里写着’R’或者’F’,R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着’F’并且面积最大。
但是rainbow和freda的OI水平都弱爆了,找不出这块土地,而蓝兔也想看freda卖萌(她显然是不会编程的……),所以它们决定,如果你找到的土地面积为S,它们将给你3*S两银子。
样例
输入样例:
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
(单调栈) $O(mn)$
主要想法同 AcWing 131. 直方图中最大的矩形。
图形总共n行m列。
1.先确定行数。然后再该行进行最大矩形的计算。
2.再最每行求出的最大值,再求一个最大值。
注意:left
和right
数组存的是左边或者右边能卡到的边界,注意这个边界是下标值。
所以在reverse
后求right
的时候需要翻转两次,即m + 1 - r[m + 1 - i]
打个比方,如图
计算原图片right[1]
的时候,实际上得计算reverse(a + 1, a + m + 1)
后的right[m + 1 - i]
,即翻转过后的图中的right[4]
。
然后计算出的right[4]
是翻转后的图中的下标,不是原图的下标。所以得再翻转一次,
即$m + 1 - right[m + 1 - i]$
时间复杂度
每行进行一次单调栈$O(m)$
总共n行,所以$O(mn)$
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int l[N], r[N], h[N][N], q[N];
char g[N][N];
int n, m;
void cal(int a[], int l[]){
int hh = 0, tt = 0;
a[0] = -1;//重要,不然会出现tt--,越界。
for (int i = 1; i <= m; i ++){
while (a[q[tt]] >= a[i]) tt --;
l[i] = q[tt] + 1;
q[++ tt] = i;
}
}
int work(int a[]){
cal(a, l);
reverse(a + 1, a + m + 1);
cal(a, r);
reverse(a + 1, a + m + 1);
int res = 0;
for (int i = 1; i <= m; i ++){
int left = l[i];
int right = m + 1 - r[m + 1 - i];
res = max(res, a[i] * (right - left + 1));
}
return res;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++){
cin >> g[i][j];
if (g[i][j] == '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;
}