网格问题

Published: by Creative Commons Licence

  • Tags:

最大权子矩形问题

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

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

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

可行矩形问题

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

给定一个$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)$。

提供一道题目

给定一个$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)$。

提供一道题目