0 前言
最近做到了很多关于求解最大子矩形的问题，写个博客稍微总结一下 (顺便整理一下模板)
1 一些基本定义
- 有效子矩形：内部不包含任何障碍点且边界与坐标轴平行的子矩形。
- 极大有效子矩形：不存在包含它且比它大的有效子矩形的有效子矩形。
- 最大(有效)子矩形：所有极大有效子矩形中最大的一个(或多个)有效子矩形。
2 两种常用的算法
算法1 基于障碍点的算法
例题1 奶牛浴场
题目描述
由于 John 建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John 决定在牛场中建造一个大型浴场。但是 John 的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John 希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于 Clevow 了。你还能帮助 Clevow 吗？
John 的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
Clevow 当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。
输入格式
输入文件的第一行包含两个整数 和 ，分别表示牛场的长和宽。
文件的第二行包含一个整数 ，表示产奶点的数量。
以下 行每行包含两个整数 和 ，表示一个产奶点的坐标。
所有产奶点都位于牛场内，即：，。
输出格式
输出文件仅一行，包含一个整数 ，表示浴场的最大面积。
样例 #1
样例输入 #1
样例输出 #1
提示
对于所有数据，，。
Winter Camp 2002
题解
这道题障碍点数较小，适合使用基于障碍点的算法实现
先将障碍点按横坐标排序(以 坐标为第一关键字， 坐标为第二关键字)
从第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
63
64
65
66
67
68
| #include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 5;
int l, w, n;
struct Point
{
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
} p[N];
int main()
{
scanf("%d%d%d", &l, &w, &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
p[++n] = Point(0, 0);
p[++n] = Point(0, w);
p[++n] = Point(l, 0);
p[++n] = Point(l, w);
int ans = 0;
int x1, y1, x2, y2;
sort(p + 1, p + n + 1, [&](Point A, Point B)
{ return A.x < B.x || A.x == B.x && A.y < B.y; });
for (int i = 1; i <= n; i++)
{
x1 = p[i].x, y1 = 0, y2 = w;
for (int j = i + 1; j <= n; j++)
{
x2 = p[j].x;
ans = max(ans, (x2 - x1) * (y2 - y1));
if (p[j].y < p[i].y)
y1 = max(y1, p[j].y);
else
y2 = min(y2, p[j].y);
}
}
for (int i = n; i >= 1; i--)
{
x2 = p[i].x, y1 = 0, y2 = w;
for (int j = i - 1; j >= 1; j--)
{
x1 = p[j].x;
ans = max(ans, (x2 - x1) * (y2 - y1));
if (p[j].y < p[i].y)
y1 = max(y1, p[j].y);
else
y2 = min(y2, p[j].y);
}
}
sort(p + 1, p + n + 1, [&](Point A, Point B)
{ return A.y < B.y || A.y == B.y && A.x < B.x; });
for (int i = 1; i < n; i++)
ans = max(ans, l * (p[i + 1].y - p[i].y));
printf("%d\n", ans);
return 0;
}
|
算法2 悬线法
例题2 玉蟾宫
题目背景
有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
题目描述
这片土地被分成 个格子，每个格子里写着 ‘R’ 或者 ‘F’，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 ‘F’ 并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 ，它们每人给你 两银子。
输入格式
第一行两个整数 ，，表示矩形土地有 行 列。
接下来 行，每行 个用空格隔开的字符 ‘F’ 或 ‘R’，描述了矩形土地。
输出格式
输出一个整数，表示你能得到多少银子，即 () 的值。
样例 #1
样例输入 #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可能会被卡，因此使用悬线法。
悬线法
悬线的定义(引用自悬线法 - OI Wiki)
悬线，就是一条竖线，这条竖线有初始位置和高度两个性质，可以在其上端点不超过当前位置的矩形高度的情况下左右移动。
对于矩形中的任意一个点 , 定义三个量 , , ，分别表示 悬线的高度 ， 悬线最多能向左拓展到的位置坐标 ， 悬线最多能向右拓展到的位置坐标 。
先考虑计算 : 如果该点为障碍点，那么其悬线高度显然为 ，反之，则为 .
再考虑计算 , 易知初始情况下
以向左拓展悬线计算 为例:
可以证明，最终每个 最多会被其他的 遍历一次，因此每次拓展的时间复杂度为
最大子矩形的面积为
整体的时间复杂度为
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;
int n, m;
char a[3];
int h[N], l[N], r[N];
int main()
{
scanf("%d%d", &n, &m);
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
l[j] = r[j] = j;
for (int j = 1; j <= m; j++)
{
scanf("%s", a);
if (a[0] == 'F')
h[j]++;
else if (a[0] == 'R')
h[j] = 0;
}
for (int j = 1; j <= m; j++)
while (l[j] != 1 && h[l[j] - 1] >= h[j])
l[j] = l[l[j] - 1];
for (int j = m; j >= 1; j--)
while (r[j] != m && h[r[j] + 1] >= h[j])
r[j] = r[r[j] + 1];
for (int j = 1; j <= m; j++)
ans = max(ans, (r[j] - l[j] + 1) * h[j]);
}
printf("%d\n", ans * 3);
return 0;
}
|
参考资料
《浅谈用极大化思想解决最大子矩形问题》, 王知昆 , 2003年集训队论文
悬线法 - OI Wiki