具体参看 浅谈用极大化思想解决最大子矩形问题 这篇论文
其实本来是想做单调栈的，但是碰巧看到了最大子矩阵问题，当然可以用单调栈做，但是我先学习了悬线法，单调栈就先留个坑之后补一下
稍微说一下我对悬线法的理解，悬线的定义是上端点覆盖了一个障碍点或达到整个矩形上端的除两端外都不包含障碍点的竖线，通俗来说就是顶端是障碍点或者顶端，不包含障碍点的竖线，首先任意一个最大子矩阵都至少含有一个悬线，而悬线往两遍扫必然包含最大子矩阵。那么目前的问题就是，怎么找到所有的悬线，由于悬线和底部的点一一对应（顶端为某一障碍点的悬线可以有多个），所以可以通过枚举底端来实现。
简单说一下步骤，这是预处理
for (int i = 1; i <= n; i++) for (int j = 2; j <= m; j++) if (map[i][j] == 1 && map[i][j - 1] == 1) //两个都不是障碍，就扩展一下 l[i][j] = l[i][j - 1]; for (int i = 1; i <= n; i++) for (int j = m - 1; j >= 1; j--) if (map[i][j] == 1 && map[i][j + 1] == 1) r[i][j] = r[i][j + 1];
核心步骤
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (map[i][j] == 1 && map[i - 1][j] == 1) { r[i][j] = min(r[i][j], r[i - 1][j]); l[i][j] = max(l[i][j], l[i - 1][j]); up[i][j] = up[i - 1][j] + 1; } ans = max(ans, (r[i][j] - l[i][j] + 1) * up[i][j]); }
下面是题目
这是luogu4171玉蟾宫的代码，一个板子题
#include <cstdio> #include <algorithm> using namespace std; const int N = 1010; int map[N][N], l[N][N], r[N][N], up[N][N]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { char s[2]; scanf("%s", s); if (s[0] == ‘F‘) map[i][j] = 1, l[i][j] = r[i][j] = j; else map[i][j] = 0, l[i][j] = 1, r[i][j] = 0; //注意一下这里，保证下面遇到这种情况是左右长度0 up[i][j] = 1; } for (int i = 1; i <= n; i++) for (int j = 2; j <= m; j++) if (map[i][j] == 1 && map[i][j - 1] == 1) l[i][j] = l[i][j - 1]; for (int i = 1; i <= n; i++) for (int j = m - 1; j >= 1; j--) if (map[i][j] == 1 && map[i][j + 1] == 1) r[i][j] = r[i][j + 1]; int ans = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (map[i][j] == 1 && map[i - 1][j] == 1) { r[i][j] = min(r[i][j], r[i - 1][j]); l[i][j] = max(l[i][j], l[i - 1][j]); up[i][j] = up[i - 1][j] + 1; } ans = max(ans, (r[i][j] - l[i][j] + 1) * up[i][j]); } printf("%d", ans * 3); return 0; }
原文：https://www.cnblogs.com/cminus/p/12375506.html