0 前言
最近做到了很多关于求解最大子矩形的问题，写个博客稍微总结一下 (顺便整理一下模板)
1 一些基本定义
- 有效子矩形：内部不包含任何障碍点且边界与坐标轴平行的子矩形。
- 极大有效子矩形：不存在包含它且比它大的有效子矩形的有效子矩形。
- 最大(有效)子矩形：所有极大有效子矩形中最大的一个(或多个)有效子矩形。
2 两种常用的算法
算法1 基于障碍点的算法
例题1 奶牛浴场
题目描述
由于 John 建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John 决定在牛场中建造一个大型浴场。但是 John 的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John 希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于 Clevow 了。你还能帮助 Clevow 吗？
John 的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
Clevow 当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。
输入格式
输入文件的第一行包含两个整数 L 和 W，分别表示牛场的长和宽。
文件的第二行包含一个整数 n，表示产奶点的数量。
以下 n 行每行包含两个整数 x 和 y，表示一个产奶点的坐标。
所有产奶点都位于牛场内，即：0≤x≤L，0≤y≤W。
输出格式
输出文件仅一行，包含一个整数 S，表示浴场的最大面积。
样例 #1
样例输入 #1
样例输出 #1
提示
对于所有数据，0≤n≤5×103，1≤L,W≤3×104。
Winter Camp 2002
题解
这道题障碍点数较小，适合使用基于障碍点的算法实现
先将障碍点按横坐标排序(以 x 坐标为第一关键字，y 坐标为第二关键字)
从第1个障碍点开始，从左至右依次扫描每个障碍点 Pi(xi,yi),i∈[1,n]
一开始设置上下边界为 y1=0,y2=w，不断通过加入新的障碍点缩小上下边界范围
即对于任何一个新加入的障碍点 Pj(xj,yj),j∈(i,n]:
如果该点位于 Pi 下方 (yj<yi)，则更新下边界 y1=max{y1,yj}
反之，如果该点位于 Pi 上方 (yj>yi)，则更新上边界 y2=min{y2,yj}
同时计算以障碍点 Pi(xi,yi),Pj(xj,yj) 所在竖直线与上下两端的极大有效子矩形面积:
Sx=(xj−xi)×(y2−y1)
同理，从右至左扫描再扫描一次
但是这样还不够，我们还没有考虑宽度与原矩形相同的极大有效子矩形
因此还需要将障碍点按纵坐标排序(以 y 坐标为第一关键字，x 坐标为第二关键字)
计算由相邻障碍点 Pi(xi,yi),Pi+1(xi+1,yi+1),i∈[1,n) 所在水平线与左右两端围成的极大有效子矩形面积:
Sy=L×(yi+1−yi)
通过以上方法求得的极大有效子矩形面积的最大值即为最大(有效)子矩形的面积
总体时间复杂度 O(n2) ( n 为障碍点数)
代码
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 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
题目描述
这片土地被分成 N×M 个格子，每个格子里写着 ‘R’ 或者 ‘F’，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 ‘F’ 并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 S，它们每人给你 S 两银子。
输入格式
第一行两个整数 N，M，表示矩形土地有 N 行 M 列。
接下来 N 行，每行 M 个用空格隔开的字符 ‘F’ 或 ‘R’，描述了矩形土地。
输出格式
输出一个整数，表示你能得到多少银子，即 (3×最大 ’F’ 矩形土地面积) 的值。
样例 #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
提示
对于 50% 的数据，1≤N,M≤200。
对于 100% 的数据，1≤N,M≤1000。
题解
这道题障碍点数可能到达 N×M ，算法1可能会被卡，因此使用悬线法。
悬线法
悬线的定义(引用自悬线法 - OI Wiki)
悬线，就是一条竖线，这条竖线有初始位置和高度两个性质，可以在其上端点不超过当前位置的矩形高度的情况下左右移动。
对于矩形中的任意一个点 (i,j) , 定义三个量 hi,j, li,j , ri,j ，分别表示 悬线的高度 ， 悬线最多能向左拓展到的位置坐标 ， 悬线最多能向右拓展到的位置坐标 。
先考虑计算 hi,j : 如果该点为障碍点，那么其悬线高度显然为 0，反之，则为 hi,j−1+1.
再考虑计算 $ l_{i, j}, r_{i, j} $ , 易知初始情况下 li,j=ri,j=j
以向左拓展悬线计算 li,j 为例:
-
如果当前已经拓展到边界，即 li,j=1 ，则不可以再进行拓展
-
如果当前点的左侧悬线高度 小于 该点悬线高度，即 hi,li,j−1<hi,j，则不可以再进行拓展
-
如果当前点的左侧悬线高度 大于等于 该点悬线高度，即 hi,li,j−1≥hi,j，则可以继续向左拓展，而且 li,j−1 位置所能拓展到最左侧的位置从 j 位置开始也必定能拓展到，可以递推求解
可以证明，最终每个 li,j 最多会被其他的 li,k 遍历一次，因此每次拓展的时间复杂度为 O(N)
最大子矩形的面积为 max{(ri,j−li,j+1)∗hi,j}
整体的时间复杂度为 O(N×M)
代码
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
