网格问题

Published: by Creative Commons Licence

  • Tags:

最大权子矩形问题

给定一个$n\times m$网格,每个网格上有一个整数,要求选择一个非空子矩形,要求子矩形中包含的数的总和最大。

我们可以暴力枚举子矩形的上下边界,现在的问题就是一个序列,要求求一段子序列使得总和最大,这是一个经典问题,可以$O(n)$求解。

整体时间复杂度为$O(n^2m)$(我们可以旋转整个网格得到时间复杂度$O(m^2n)$)。

二维最大面积子矩形问题

给定一个矩形大厅,大厅中共有$n$根柱子,第$i$根柱子的坐标为$(x_i,y_i)$,柱子很细,可以视作一个点。要求在大厅布置一个矩形舞台,要求舞台和柱子不能重合(允许落在边缘,但不允许落在内部),问舞台的最大面积。

提供一道题目

可以发现舞台的边缘要么与大厅相接,要么与柱子相接。因此直接就给出了一个$O(n^5)$的算法。

我们可以暴力枚举矩形的上边界,之后在考虑不同的下边界。当上下边界固定的时候,落在上下边界中的点的横坐标记作$t_1,t_2,\ldots,t_k$,要让面积最大,这时候很显然问题等价于找到距离最大的一对相邻的横坐标。这个可以$O(n)$计算。于是时间复杂度优化到了$O(n^3)$。

下面我们考虑进一步优化,当下边界从$j$下移到$j-1$的时候,一些新的点会被加入考虑。实际上考虑加入一个新的点$m$,这个点左边横坐标为$l$,右边横坐标为$r$,其将原来某个连续的空间$[l,r]$切割为两部分$[l,m]$和$[m,r]$。这意味着相邻坐标最大距离有可能减小,减小不好处理,我们需要借助平衡树才好处理,这样的时间复杂度为$O(n^2\log_2n)$。

虽然区间分裂不好处理,但是如果我们反过来处理,我们从下向上枚举下边界,这时候就变成了一开始区间全部分裂,之后不断删除点,区间合并。这时候我们就可以很简单的维护最大区间,时间复杂度为$O(n^2)$。

可行矩形问题

一个网格,每个网格上面写着数字0或1。一个矩形是可行矩形,当且仅当矩形中只包含数字0。

题目1:给定一个$n\times m$网格,每个网格上写着数字0或1。要求选择一个非空可行矩形,满足矩形面积最大。

如果我们给0替换为1,1替换为负无穷,问题就变成了最大权子矩形问题,我们就有了$O(n^2m)$的算法。

我们可以暴力枚举子矩形的上边界$i$,并且对每个$j=1,\ldots,m$,记$f_i(j)$表示$(i,j)$上方的第一个1出现的纵坐标(如果不出现记做$n+1$)。我们知道一个最大面积子矩形必定不能再向上,左,右继续扩大,不能向上扩大是因为上方有1。我们分别考虑这个1出现的位置,其可能为$(f_i(j),j)$,对于给定1的位置,我们可以容易确定左右边界,左右边界可以通过递增队列来实现,因此对于给定$i$,我们可以$O(m)$算出相关的所有可能结果。

总的时间复杂度为$O(nm)$。

提供一道题目

题目2:给定一个$n\times m$网格,每个网格上写着数字0或1。要求对于$1\leq i\leq n,1\leq j\leq m$输出$f(i,j)$,其中$f(i,j)$表示高为$i$宽度为$j$的可行矩形总数。

首先如果我们暴力枚举左上角顶点,可以得到$O((nm)^2)$的算法。

考虑枚举上下边界,我们可以发现一列可以被选择,当且仅当在上下边界内这一列都是$0$。这时候我们的到一个01序列。我们需要统计不同宽度的连续0序列的数目。我们可以将01序列划分为若干个不可扩增的0序列,并记录它们的长度为$w_1,\ldots,w_k$,记录$C(i)$表示$i$在$w$序列中出现的次数。记$g(i)$为长度为$i$的0序列数目,可以发现$g(i)=g(i+1)+\sum_{j=i}^m w_j$。这个我们可以通过后缀和可以$O(m)$求出。因此现在我们得到了$O(n^2m)$的算法。

接下来我们进一步优化。考虑我们处理了上边界为$U$,下边界为$D$的情况,这时候我们将$D$增大$1$,考虑会发生什么。我们可以发现一些$w$中的元素被分裂成两个,这对应于$C(i)$的常数次加减操作。并且每一列在这个过程中都最多仅贡献一次,因此仅考虑这些操作实际上是$O(m)$级别的。但是还有一个问题,我们在枚举下边界的时候每一行都需要复制$C$,这显然是很大的开销,我们可以通过维护前缀和的技术来实现,这样我们只需要$O(m)$级别的修改即可。还有一个问题就是对应不同的上边界我们需要维护不同的前缀和,但是由于我们最后只需要算出$C(i)$的总和而已,因此我们把这些前缀和数组合并在一起,一起维护即可。这样对于每个固定的上边界,我们的时间复杂度为$O(m)$。最后跑一次我们提到的计算$g$的算法,算出所有的$f(i,j)$即可。总的时间复杂度为$O(nm)$。

提供一道题目