懸線法是用來處理子矩陣相關的問題，在一個矩形中尋找一個最大的滿足條件的矩陣
懸線法的基本思路，維護三個陣列，l[N][N],r[N][N],up[N][N]，
l[N][N]:用來記錄在當前這個位置滿足條件的左邊界，也就是可以往左延伸到哪一列，
r[N][N]:用來記錄當前和這個位置滿足條件的右邊界，也就是可以往右延伸到哪一列
up[N][N]:用來記錄當前這個位置滿足條件高度，也就是可以往上延伸到哪個位置
eg：
P1169 [ZJOI2007]棋盤制作.
國際象棋是世界上最古老的博弈游戲之一，和中國的圍棋、象棋以及日本的將棋同享盛名，據說國際象棋起源于易經的思想，棋盤是一個8 \times 88×8大小的黑白相間的方陣，對應八八六十四卦，黑白對應陰陽，
而我們的主人公小Q，正是國際象棋的狂熱愛好者，作為一個頂尖高手，他已不滿足于普通的棋盤與規則，于是他跟他的好朋友小W決定將棋盤擴大以適應他們的新規則，
小Q找到了一張由N \times MN×M個正方形的格子組成的矩形紙片，每個格子被涂有黑白兩種顏色之一，小Q想在這種紙中裁減一部分作為新棋盤，當然，他希望這個棋盤盡可能的大，
不過小Q還沒有決定是找一個正方形的棋盤還是一個矩形的棋盤（當然，不管哪種，棋盤必須都黑白相間，即相鄰的格子不同色），所以他希望可以找到最大的正方形棋盤面積和最大的矩形棋盤面積，從而決定哪個更好一些，
于是小Q找到了即將參加全國資訊學競賽的你，你能幫助他么？
對這個三個矩陣進行操作后就可以的得到這個子矩陣的長和寬
長為
int len=r[i][j]-l[i][j]+1;
寬為
up[i][j]
以此不斷迭代可以得到最大的子矩陣面積
ans2=max(ans2,up[i][j]*len);
測驗樣例：
3 7
0 0 1 0 1 0 1
1 0 1 0 1 1 0
1 0 1 0 1 0 1
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
typedef long long ll;
int ma[N][N],l[N][N],r[N][N],up[N][N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&ma[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
l[i][j]=j;
r[i][j]=j;
up[i][j]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=2;j<=m;j++)
{
if(ma[i][j]!=ma[i][j-1])
{
l[i][j]=l[i][j-1];
}
}
for(int j=m-1;j>=0;j--)
{
if(ma[i][j]!=ma[i][j+1])
{
r[i][j]=r[i][j+1];
}
}
}
首先需要根據定義求出l[N][N],r[N][N],up[N][N]三個矩陣
int ans1=0,ans2=0;
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1)continue;
if(ma[i][j]!=ma[i-1][j])
{
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]);
}
int len=r[i][j]-l[i][j]+1;
ans1=max(ans1,min(up[i][j],len));
ans2=max(ans2,up[i][j]*len);
}
}
cout<<ans1*ans1<<endl;
cout<<ans2<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/289947.html
標籤：其他