悬线法

wner / 2024-01-26 / 原文

介绍
悬线法主要由up[],l[],r[]构成，其含义分别是，在某处符合题目条件的情况下，线条（抽象概念）能走到的最上边，最左边和最右边的位置。
最后统计所有子矩阵中最大的子矩阵。
1.洛谷4147玉蟾宫

点击查看代码

#include<iostream>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define ll long long
char a[1001][1001];
int up[1001][1001],l[1001][1001],r[1001][1001];

signed main()
{
     cin.tie(NULL);
     cout.tie(nullptr);
     ios_base::sync_with_stdio(false);
     int n,m;
     cin>>n>>m;
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
     {
         cin>>a[i][j];
         if(a[i][j]=='F')
         up[i][j]=1;
         l[i][j]=r[i][j]=j;


     }
     for(int i=1;i<=n;i++)
 {
     for(int j=2;j<=m;j++)
     {
         if(a[i][j]=='F'&&a[i][j-1]=='F')
         l[i][j]=l[i][j-1];

     }
     for(int j=m-1;j>=1;j--)
     {
        if(a[i][j]=='F'&&a[i][j+1]=='F')
            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]=='F'&&a[i-1][j]=='F')
            {
               up[i][j]=up[i-1][j]+1;
               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));
        }

     }
     cout<<ans*3;
     return 0;
}

2.洛谷1387最大正方形

点击查看代码

#include<iostream>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define ll long long
int a[1001][1001];
int up[1001][1001],l[1001][1001],r[1001][1001];

signed main()
{
     cin.tie(NULL);
     cout.tie(nullptr);
     ios_base::sync_with_stdio(false);
     int n,m;
     cin>>n>>m;
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
     {
         cin>>a[i][j];
         if(a[i][j]==1)
         up[i][j]=1;
         l[i][j]=r[i][j]=j;


     }
     for(int i=1;i<=n;i++)
 {
     for(int j=2;j<=m;j++)
     {
         if(a[i][j]==1&&a[i][j-1]==1)
         l[i][j]=l[i][j-1];

     }
     for(int j=m-1;j>=1;j--)
     {
        if(a[i][j]==1&&a[i][j+1]==1)
            r[i][j]=r[i][j+1];
     }
}
      int ans=0,re=0;
     for(int i=1;i<=n;i++)
     {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==1&&a[i-1][j]==1)
            {
               up[i][j]=up[i-1][j]+1;
               l[i][j]=max(l[i][j],l[i-1][j]);
               r[i][j]=min(r[i][j],r[i-1][j]);

            }
            re=min(up[i][j],r[i][j]-l[i][j]+1);
            ans=max(ans,re);
        }

     }
     cout<<ans;
     return 0;
}