题目描述
有一天,小猫 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
解题思路
这个题目很巧妙,但是归根结底还是单调栈问题,最重要的一个转化我们可以看下图上方的转化,我们可以按照每一列从上往下看,只要遇见了R那么就变0,否则就是上一个加一。最后生成的结果其实就是每一个点上面可以延伸的最大长度。最终我们可以将每一行看做是一个直方图,求出每一行能形成的直方图最大面积就好了。这一步的原理其实就是,我们可以枚举一行中的每个点(假设这一行是最下行),我们可以延伸的长度其实就是我们选取连续点的最小值。那么我们枚举每一行所有点。假设我们的延伸长度就是我们这一个点的长度。那么按照之前的直方图中最大矩形的做法,我们可以使用单调栈求出左边界右边界。最后求出面积。
代码
import java.io.*;
import java.util.*;
class Main{
public static int N = 1010,n,m;
public static int[][] g = new int[N][N];
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static long work(int i){
//处理每一行 的最大矩形
long res = 0;
int[] r = new int[N],l = new int[N],stack = new int[N];
int hh = 0;
//处理左边界
for(int j = 1;j <= m;j++){
while(hh != 0 && g[i][j] <= g[i][stack[hh]]) hh--;
l[j] = stack[hh] + 1;
stack[++hh] = j;
}
//处理右边界
hh = 0;
stack[0] = m + 1;
for(int j = m;j >= 1;j--){
while(hh != 0 && g[i][j] <= g[i][stack[hh]]) hh--;
r[j] = stack[hh] - 1;
stack[++hh] = j;
}
res = 0;
//计算最大矩形
for(int j = 1;j <= m;j++)
res = Math.max(res,(r[j] - l[j] + 1) * g[i][j]);
return res;
}
public static void main(String[] args)throws Exception{
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);m = Integer.parseInt(s1[1]);
for(int i = 1;i <= n;i++){
String[] s2 = br.readLine().split(" ");
for(int j = 1;j <= m;j++)
if(s2[j-1].equals("F")) g[i][j] = g[i-1][j] + 1;
}
long res = 0;
for(int i = 1;i <= n;i++)
res = Math.max(res,work(i));
System.out.print(res * 3);
}
}