浅谈悬线法

## 悬线法的用途 悬线法是一种求解给定矩阵中的极大矩阵的算法。 所谓“给定矩阵中的极大矩阵”是指一个矩形中有一些障碍点，求内部不包含任何障碍点且边界与坐标轴平行的子矩形。 ## 相关定义 & 定理 我们定义**有效子矩形**为内部不包含任何障碍点且边界与坐标轴平行的子矩形。  显然图中第一个矩形是有效子矩形而第二个矩形不是。 对于一个有效子矩形，如果不存在包含它且比它大的有效子矩形则称它为**极大有效子矩形**，而**最大有效子矩形**为极大有效子矩形中最大的一个（或多个）。 由此我们可以得到定理：**一个极大有效子矩形的四条边一定不能向外扩展**。也就是说，一个极大有效子矩形的一条边，要么与矩形边界重合，要么往外一格就是障碍点，这个定理的证明很显然，如果有边可以向外扩展，我们要求最大有效子矩形，一定会向外扩展以扩大面积。 ## 悬线法 对于此类问题，我们显然需要一种快速的方法求解（暴力效率极低）。 我们求一个最大有效子矩形，一定是极大有效子矩形中的一个，也就是说，我们可以求所有极大有效子矩形，然后扫描它们，求出面积最大值。 所以现在问题就转变为了求所有的极大有效子矩形。 我们引入悬线的概念。我们称**除两个端点外不覆盖任何障碍点的竖直线段**为有效竖线，**上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线**为悬线。  图中三条线均为悬线。 我们可以发现，每一个极大有效子矩形都可以由一条悬线向左右尽可能的移动得到，也就是说，我们只要处理出每条悬线的极大有效子矩形就可以求出所有的极大有效子矩形。  图为将一条悬线左右尽可能移动得到的极大子矩形。 很容易得出每条悬线是由它底部的点唯一确定的，也就是说，在一个 $N*M$ 的矩形中最多只有 $(N-1)*M$ 条悬线。 既然每条悬线都由它底部的点唯一确定，那我们只需要枚举这个点对应的悬线长度（这个点能够往上扩展的最大长度）和这个悬线能够往左右扩展的最大长度就可以求解。 定义 $a_{i,j}$为矩阵中是否有障碍点，若 $a_{i,j}=1$则有障碍点，反之则无障碍点；$up_{i,j}$ 为点 $(i,j)$ 对应的悬线长度，初始化当点 $(i,j)$ 不是障碍点时 $up_{i,j}=1$. 显然 $up_{i,j}$很容易通过递推求出，也就是说，当点 $(i-1,j)$ 不是障碍点时，$up_{i,j}=up_{i-1,j}+1$. 关键在于如何求出每条悬线能够往左右扩展的最大长度。我们知道，一条悬线往左边能扩展到的最大长度一定是它包含的所有点能往左边扩展到的最大长度的最小值，往右同理，这就是说，我们可以通过枚举悬线上每个点往左右扩展到的最大长度来求解一条悬线往左右扩展到的最大长度。 令 $l_{i,j},r_{i,j}$ 分别为点 $(i,j)$ 往左/右能扩展到第几列，初始化即为当点 $(i,j)$ 不是障碍点时 $l_{i,j}=r_{i,j}=j$. $l_{i,j},r_{i,j}$ 也很容易通过递推求出，当点 $(i,j)$ 及它左边的点 $(i,j-1)$ 均不为障碍点时，$l_{i,j}=l_{i,j-1}$.同理可得 $r_{i,j}=r{i,j+1}$,这里需要注意递推时的循环顺序，$l_{i,j}$ 需要从左到右推，即 $j$ 从 $2$ 到 $m$,而 $r_{i,j}$ 需要从右到左推，即 $j$ 从 $m-1$ 到 $1$. 递推部分的代码 ```cpp for(register int i=1;i<=n;++i) for(register int j=2;j<=m;++j) if(!a[i][j]&&!a[i][j-1]) l[i][j]=l[i][j-1]; for(register int i=1;i<=n;++i) for(register int j=m-1;j;--j) if(!a[i][j]&&!a[i][j+1]) r[i][j]=r[i][j+1]; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) if(!a[i][j]&&!a[i-1][j]) up[i][j]=up[i-1][j]+1; ``` 到这里，我们已经预处理完了 $up_{i,j},l_{i,j},r_{i,j}$,接下来需要求出每条悬线所能向左右扩展的最大长度了。 我们依然使用相同的数组 $l,r$ 表示点 $(i,j)$ 向左/右能够扩展到第几列，根据一条悬线往左边能扩展到的最大长度一定是它包含的所有点能往左边扩展到的最大长度的最小值，我们可以得到状态转移方程 $l_{i,j}=max(l_{i,j},l_{i-1,j})$,往右同理，即 $r_{i,j}=min(r_{i,j},r_{i-1,j})$,这里需要弄清楚向左最多扩展的列数是所有列数中的最大值（最右），向右最多扩展的列数是所有列数中的最小值（最左）。 这部分的代码（注意 $i$ 要从 $2$ 开始枚举） ```cpp for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) { if(i>=2&&!a[i][j]&&!a[i-1][j]) { l[i][j]=max(l[i][j],l[i-1][j]); r[i][j]=min(r[i][j],r[i-1][j]); } ans=max(ans,up[i][j]*(r[i][j]-l[i][j]+1)); } ``` 悬线法的时间复杂度为 $O(NM)$,空间复杂度为 $O(NM)$. ## 例题选讲 [P4147玉蟾宫](https://www.luogu.com.cn/problem/P4147) 题意：给定一个只含 "F" 与 "R" 的矩阵，求只含 "F" 的子矩阵的最大面积乘三是多少。 这一题就是明显的悬线法了，矩阵中 "L" 为无障碍点，"R" 为有障碍点，然后跑一遍悬线法模板即可 代码（要注意读入要对空格和回车作出处理，`cin` 自动屏蔽空格和回车） ```cpp #include <cstdio> #include <algorithm> #include <iostream> #define MAXN 1005 using namespace std; int n,m,ans=-1; int a[MAXN][MAXN]; int l[MAXN][MAXN],r[MAXN][MAXN],up[MAXN][MAXN]; signed main() { scanf("%d%d",&n,&m); char ch; for(register int i=1;i<=n;++i) { for(register int j=1;j<=m;++j) { cin>>ch; if(ch=='R') a[i][j]=1; else { l[i][j]=r[i][j]=j; up[i][j]=1; } } } for(register int i=1;i<=n;++i) for(register int j=2;j<=m;++j) if(!a[i][j]&&!a[i][j-1]) l[i][j]=l[i][j-1]; for(register int i=1;i<=n;++i) for(register int j=m-1;j;--j) if(!a[i][j]&&!a[i][j+1]) r[i][j]=r[i][j+1]; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) if(!a[i][j]&&!a[i-1][j]) up[i][j]=up[i-1][j]+1; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) { if(i>=2&&!a[i][j]&&!a[i-1][j]) { l[i][j]=max(l[i][j],l[i-1][j]); r[i][j]=min(r[i][j],r[i-1][j]); } ans=max(ans,up[i][j]*(r[i][j]-l[i][j]+1)); } printf("%d\n",ans*3); return 0; } ``` 悬线法已经足够解决绝大部分最大子矩阵问题了，但不排除有毒瘤出题人把 $N,M$ 出的特别大而障碍点个数特别小的情况，这个时候我们可以利用极大化思想去实现一个 $O(S^2)$（S为障碍点个数）的算法，有兴趣的读者可以自行探究。