悬线法

介绍

可以用来解决最大子矩阵问题

原理分析

设L/R[i][j]表示自点（i,j）向左/右在不经过障碍点情况下能达到的最远点横坐标（图是数组画法时的横坐标），up[i][j]表示（i，j）向上能达到的最远点，初始化为up[i][j] = 1;R[i][j] = L[i][j] = j;得到的是（R-L+1） * up的一个矩阵，如果上面也是合法矩形，那么就合并两个矩形更新答案。但是是否不合并更好呢？当然可能，不过这种情况下上下两矩形的(R - L + 1)不同，在不接合的点会考虑此情况。

例题

Luogu-P4147

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mid  ((L + R) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x) {
    char c = getchar(),f = 1;x = 0;
    for(;c ^ '-' && !isdigit(c);c = getchar());
    if(c == '-') c = getchar(),f = -1;
    for(;isdigit(c);c = getchar()) x = (x<<1) + (x<<3) + (c ^ '0');
    x *= f;
}
template<typename xxx>void print(xxx x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int maxn = 2010;
const int inf = 0x7fffffff;
const int mod = 1e9 + 7;
char s[maxn];
int a[maxn][maxn];
int R[maxn][maxn];//表示从(i,j)这个点出发向右能到达最远的点横坐标 
int L[maxn][maxn];//表示从(i,j)这个点出发向左能到达最远的点横坐标 
int up[maxn][maxn];//向上到达最远点的距离 
int n,m;
int main() {
    int ans = 0;
    read(n);read(m);
    for(rint i = 1;i <= n; ++i) {
        for(rint j = 1;j <= m; ++j) {
            scanf("%s",s);
            if(s[0] == 'F') a[i][j] = 1;
            up[i][j] = 1;
            R[i][j] = L[i][j] = j;
        }
    }
    for(rint i = 1;i <= n; ++i) {
        for(rint j = 2;j <= m; ++j) {
            if(a[i][j] && a[i][j - 1]) {
                L[i][j] = L[i][j - 1];
            }
        } 
    } 
    for(rint i = 1;i <= n; ++i) {
        for(rint j = m - 1; j; --j) {
            if(a[i][j] && a[i][j + 1]) {
                R[i][j] = R[i][j + 1];
            }
        } 
    } 
    for(rint i = 1;i <= n; ++i) {
        for(rint j = 1;j <= m; ++j) {
            if(i > 1) {
                if(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]);
                    up[i][j] = up[i - 1][j] + 1;
                }
            }
            ans = max(ans,(R[i][j] - L[i][j] + 1) * up[i][j]);
        }
    }
    print(ans * 3);
    return 0;
}
/*

*/

悬线法

原文：https://www.cnblogs.com/Thomastine/p/11827955.html