很经典的国家集训队论文:浅谈用极大化思想解决最大子矩形问题
最大子矩形问题:在一个给定的矩形网格中有一些障碍点,要找出网格内部不包含任何障碍点,且边界与坐标轴平行的最大子矩形。
悬线法 $O(nm)$
个人理解:枚举在子矩形底边上的一个点,将它尽可能地向上扩展成一条高线,然后将这条高左右尽可能地平移得到一个矩形,用此矩形更新答案。
枚举的复杂度已经达到了 $O(nm)$,所以我们需要预处理扩展和平移操作。
我们可以dp(或者叫递推也行)预处理:将每个点尽可能向上、向左、向右扩展到的位置存在数组 $u[][],l[][],r[][]$ 中(当然,存向上、向左、向右扩展的长度也行,但存位置对求答案来说更方便一点)1
2
3
4
5
6For i = 1 to n
For j = 1 to m
u[i][j] = (能从(i-1,j)走到(i,j)) ? u[i-1][j] : i;
l[i][j] = (能从(i,j-1)走到(i,j)) ? l[i][j-1] : j;
For j = m to 1
r[i][j] = (能从(i,j+1)走到(i,j)) ? r[i][j+1] : j;
预处理后我们得到了点 $(i,j)$ 的高线。但是对于向左和向右,我们需要知道的不是每个点向左向右扩展的位置,而是每条高线向左向右扩展的位置,这个问题我们可以递推出来:1
2
3
4
5For i = 2 to n
For j = 1 to m
if 能从(i-1,j)走到(i,j)
l[i][j] = max(l[i][j], l[i-1][j]
r[i][j] = min(r[i][j], r[i-1][j]
矩形面积就是 $(r[i][j] - l[i][j] + 1) * (i - u[i][j] + 1)$
如此以来,我们就 $O(nm)$ 地解决了这个问题。
单调栈 $O(nm)$
将每个点尽可能向上、向左、向右扩展到的长度存在数组 $u[][],l[][],r[][]$ 中。具体做法如下:For i = 1 to n
枚举矩形底边,对每一次枚举维护一个单增栈,存储的数据包括高度与宽度,For j = 1 to m
,如果当前点高度大于栈顶元素高度,就直接入栈;否则,不断弹出栈顶元素,最后将所有弹出元素的宽度之和加上自身宽度作为新的宽度入栈。这样,我们就得到了一个点向左能扩展的最大长度(手动模拟一下就清楚了)。同理,For j = m to 1
就可以求出一个点向右扩展的最大长度。(当然,不用反过来for也能求出来,但是反过来for一遍挺方便的,何乐而不为?)
单调栈做法的思想其实和悬线法本质上是一样的,只不过省去了递推那一步。
注意:有些题并不是两种方法都可以的
$O(S^2)$算法
例题
hdu1506 / poj2559
底边已经定了,直接考察单调栈
1 |
|
hdu2830
枚举底边,按高度排个序,就变成了上一题。
有趣的是,由于排了序,我们不用写单调栈,运用它的思想即可。
1 |
|
hdu1505 / poj1964
悬线法
1 |
|
poj3494
悬线法
1 |
|
hdu2870
最大子矩形一定要么全是 $a$,要么全是 $b$,要么全是 $c$。
假设最大子矩形全是 $a$,那么把所有能变成 $a$ 的全变成 $a$ 一定比不变某些字母更好,以此求一次答案;同理,再全变成 $b$ 求一次答案,再全变成 $c$ 求一次答案。
1 |
|
[ZJOI2007]棋盘制作
悬线法
1 |
|
奶牛浴场
洛谷上的题解 很详尽
1 |
|