P4147「玉蟾宫」

1. 题目

题目链接:P4147「玉蟾宫」

题目背景

有一天,小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。

题目描述

这片土地被分成 N×MN\times M 个格子,每个格子里写着 R 或者 FR 代表这块土地被赐予了 rainbow,F 代表这块土地被赐予了 freda。

现在 freda 要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着 F 并且面积最大。

但是 rainbow 和 freda 的 OI 水平都弱爆了,找不出这块土地,而蓝兔也想看 freda 卖萌(她显然是不会编程的……),所以它们决定,如果你找到的土地面积为 SS,它们每人给你 SS 两银子。

输入格式

第一行两个整数 NNMM,表示矩形土地有 NN 行 MM 列。

接下来 NN 行,每行 MM 个用空格隔开的字符 FR,描述了矩形土地。

输出格式

输出一个整数,表示你能得到多少银子,即「3×3\times最大 F 矩形土地面积」的值。

输入输出样例

输入 #1

1
2
3
4
5
6
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

输出 #1

1
45

说明/提示

对于 50%50\% 的数据,1N1\leq NM200M\leq 200

对于 100%100\% 的数据,1N1\leq NM1000M\leq 1000

2. 题解

分析

典型求最大子矩阵和问题,即求一个 M×NM \times N 矩阵中的子矩阵元素和的最大值。这可以用单调栈解决。对于每一行的每一列元素,往上计算连续的 F 的个数,即得到以每一行为基准的一个条形统计图,每个列对应一个条形矩形,矩形的宽为 11 ,高即为该元素往上计算连续的 F 的个数,这就是典型的计算矩形统计图的最大内矩形面积的问题,用 O(N)O(N) 的单调栈完美解决。由于有 NN 行,每一行都构造出一个矩形统计图,故总复杂度为 O(N2)O(N^2)

代码

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
66
67
68
69
70
#include <bits/stdc++.h>
#define ll int
#define MAXN 1005
using namespace std;

// 矩形统计图
struct RC {
ll i;
ll v;
RC():i(0), v(0) {}
RC(ll _i, ll _v): i(_i), v(_v) {}
};


// 计算最大子矩阵面积
ll maxRectangle(ll *A, ll n) {
ll ans = 0;
ll depth = 0;
RC stack[MAXN];
stack[depth] = RC(-1,-1);
for(ll i = 0; i < n; ++i) {
RC t(i,A[i]);
ll sdepth = depth;
while(depth && stack[depth].v >= A[i]) {
ans = max(ans, (stack[sdepth].i-stack[depth-1].i)*stack[depth].v);
--depth;
}
stack[++depth] = t;
}
ll sdepth = depth;
while(depth) {
ans = max(ans, (stack[sdepth].i-stack[depth-1].i)*stack[depth].v);
--depth;
}
return ans;
}

int main()
{
ll n, m;
ll a[MAXN][MAXN], b[MAXN][MAXN];
scanf("%d%d", &n, &m);
for(ll i = 0; i < n; ++i) {
for(ll j = 0; j < m; ++j) {
char str[2];
scanf("%s", str);
if(str[0] == 'R') {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
for(ll j = 0; j < m; ++j) b[0][j] = a[0][j];
for(ll i = 1; i < n; ++i) {
for(ll j = 0; j < m; ++j) {
if(a[i][j]) {
b[i][j] = b[i-1][j] + 1;
} else {
b[i][j] = 0;
}
}
}
ll ans = 0;
for(ll i = 0; i < n; ++i) {
ans = max(ans, maxRectangle(b[i], m));
}
printf("%d\n", 3*ans);
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!