悬线法练习

在此感谢那个网名叫顾z的人。

悬线法：

目标：求给定矩阵中满足条件的最大子矩阵

方法：left[i][j]表示(i,j)所能到达的最左位置 , right[i][j]类似 , up[i][j]表示往上扩展的最大长度。

递推公式：
left[i][j]=max(left[i][j],left[i?1][j])
right[i][j]=min(right[i][j],right[i-1][j])

正确性显然， 适用性可能不是那么通用。

讲解更好的博客：https://www.luogu.com.cn/blog/RPdreamer/p1169

//悬线法求解最大规模子矩阵板子

int main()
{
    
    cin >> n >> m;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            cin >> a[i][j];
            left[i][j] = right[i][j] = j;
            up[i][j] = 1;
        }
    
    for(int i=1; i<=n; ++i)
        for(int j=2; j<=n; ++j)
            if(……)
                left[i][j] = left[i][j-1];
    
    for(int i=1; i<=n; ++i)
        for(int j=n-1; j>=1; --j)
            if(……)
                right[i][j] = right[i][j+1];
    
    //处理up=1时的right与left数组
    
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            
            if(i>1 && ……)
            {
                
                left[i][j] = max(left[i][j], left[i-1][j]);
                right[i][j] = min(right[i][j], right[i-1][j]);
                up[i][j] = up[i-1][j] + 1;
            }
            
            /* calc ans */
            
            
            
        }
        
    cout << ans;
        
    
    return 0;
    
 } 

例题：https://www.luogu.com.cn/problem/P1387

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;

int n, m, a[maxn][maxn];
int up[maxn][maxn], l[maxn][maxn], r[maxn][maxn];

int main()
{
    
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            scanf("%d", &a[i][j]);
            l[i][j] = r[i][j] = j;
            up[i][j] = 1;
        }
        
    for(int i=1; i<=n; ++i)
        for(int j=2; j<=m; ++j)
            if(a[i][j-1] && a[i][j])
                l[i][j] = l[i][j-1];
    
    for(int i=1; i<=n; ++i)
        for(int j=m-1; j>=1; --j)
            if(a[i][j+1] && a[i][j])
                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(a[i][j] == 1)
        {
            
            if(i>1 && a[i-1][j] && a[i][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;
            }
            
            int a = r[i][j] - l[i][j] + 1;
            int b = up[i][j];
            ans = max(ans, min(a,b));
            
        }
    
    cout << ans;
    
    return 0;
    
}

例题：https://www.luogu.com.cn/problem/P1169

#include<bits/stdc++.h>
using namespace std;


const int maxn = 2005;

int n, m, a[maxn][maxn];

int l[maxn][maxn], r[maxn][maxn], up[maxn][maxn];

int main()
{
    
    cin >> n >> m;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            scanf("%d", &a[i][j]);
            l[i][j] = r[i][j] = j;
            up[i][j] = 1;
        }
        
    for(int i=1; i<=n; ++i)
        for(int j=2; j<=m; ++j)
            if(a[i][j] != a[i][j-1])
                l[i][j] = l[i][j-1];
    
    for(int i=1; i<=n; ++i)
        for(int j=m-1; j>=1; --j)
            if(a[i][j] != a[i][j+1])
                r[i][j] = r[i][j+1];
    
    int ans1 = 0, ans2 = 0;
    
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            
            if(i>1 && 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;
            }
            
            int a = r[i][j] - l[i][j] + 1;
            int b = up[i][j];
            
            ans1 = max(ans1, min(a,b)*min(a,b) );
            ans2 = max(ans2, a*b);
            
        }
    
    cout << ans1 << '\n' << ans2;
    
    return 0;
    
}

悬线法练习

原文：https://www.cnblogs.com/tztqwq/p/12312082.html