0%

悬线法

发表于 更新于 分类于
一种最大子矩阵DP的解法

悬线法，这个名词是我在做P4147 玉蟾宫时遇到的。

此题题目大概意思：计算01矩阵内最大的全0矩形面积。

本题自然是可以用单调栈做的了，此处不做赘述。重点讲下悬线法。

如果矩阵是n$$m，则悬线法的时间复杂度最差情况是O($nm$)。

其大致原理如下：

$\sf\color{darkviolet}{\text{悬线：指一条上端点覆盖了一个障碍点或与矩阵边界重合，且除端点外，不覆盖任何障碍点的竖线}}$

$\sf\color{lime}{\text{几个关键字：以上界或某个障碍点作为上端点，除端点不覆盖任何障碍点，竖线。}}$

所以就有了模糊的想法：以一条悬线左右平移直到遇到障碍点，直到其某个瞬间无法保持悬线定义为止。过程中扫过的矩形中必定包含了所求矩形。

则我们可以通过枚举悬线的下端点，进而枚举到悬线。下端点的数量不会超过n*m，而P4147这道题恰好是较密的障碍分布，所以枚举这步就已经达到了时限，试图O(1)完成直线的平移操作。

O(1)的实现方法很单调：要么套非递推公式算，要么记信息用。此处我们以空间换时间，采用后者的记的方式。

对于一个悬线，其平移方式无非两种：左右。但悬线在某些条件下是可以乡下继续延伸的，自然能伸则伸，无需记录。为了记录并比较矩形面积，继续引入悬线的高。

$\sf\color{lime}{\text{所以对于一个以点(i,j)为下端点的悬线，目前我们要记的有三样：}}$

$\sf\color{red}{\text{延伸左界l[i][j]，延伸右界r[i][j]，高度h[i][j]}}$

那么我们充分利用之前信息，保证在O(n*m)时间内通过递推得到三个值即可。

递推的初始条件比较显然：高度为1的可以左右一直延伸到左右界，l,r,h均可知。

初始条件有了，怎么递推？

$\mathcal h[i][j]=h[i-1][j]+1$ 以行数i为底的高度势必比i-1的高1。

$\mathcal l[i][j]=max(l[i][j],l[i-1][j])$ 向左延伸，一定要将就靠右的才符合条件。

$\mathcal r[i][j]=min(r[i][j],r[i-1][j])$ 向右延伸，一定要将就靠左的才符合条件。

信息有了，对于每条悬线，计算面积用时就是O(1)的。

$\mathcal {S=(r[i][j]-l[i][j])*h[i][j]}$，浅显易懂。

最终，最坏时间复杂度归于O(n*m)，在稀疏障碍图中，由于下端点数量不多，该算法效率极高。

以下是P4147的关键代码部分:

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
//初始化部分
for(ri i=1; i<=n; i++)
	{
		for(ri j=1; j<=m; j++)
		{
			rd:
			c=getchar();
			if(c!='F'&&c!='R')
			{
				goto rd;
			}
			v[i][j]=(c=='F');//F for 1 & R for 0
			l[i][j]=j;
			r[i][j]=j;
			h[i][j]=1;
		}
	}
//转移部分
for(ri i=1;i<=n;i++)
	{
		for(ri j=1;j<=m;j++)
		{
			if(i>1&&v[i][j]&&v[i-1][j])
			{
				r[i][j]=min(r[i][j],r[i-1][j]);
				l[i][j]=max(l[i][j],l[i-1][j]);
				h[i][j]=h[i-1][j]+1;
			}
			ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);
		}
	}

练习：

笔者注：对于奶牛浴场这种数组存不下的题，要记得灵活应变，不能直接套用格式。