当前位置:网站首页>悬线法学习笔记

悬线法学习笔记

2021-08-08 11:12:48 Dijkstra6627

背景

小王闲来无事在家刷题,遇到了一个 [ZJOI2007 棋盘制作](ZJOI2007 棋盘制作 https://www.luogu.com.cn/problem/P1169 )

显然,与这道题相类似的题目还有很多,都是给定一个大网格然后问满足某某条件的最大矩形/正方形等等。这种题目如果暴力法枚举的话其时间复杂度可能一度达到 \(\Theta (n^5)\),是完全没办法接受的,所以我们引入一个非常厉害的解决条件小矩阵问题的方法——悬线法。

题目引入—— ZJOI 2007 棋盘制作

给定一个 \(n*m\)\(01\) 网格,\(n,m\le 2000\),问其中最大的 \(01\) 交替出现的正方形和矩形的大小。

悬线法是什么呢?我们先定义三个数组:\(l_{i,j},\ \ r_{i,j},\ \ u_{i,j}\),它们分别表示,从 \((i,j)\) 这个位置可以向左,右,上达到的最远的点的位置。

咱们可以把它感性理解为,有一根横着的线,穿过 \((i,j)\) ,并且尝试向两侧延伸,这就是维护 \(l_{i,j},\ r_{i,j}\),还有一个同样的竖着的线,维护 \(u_{i,j}\)

在开始的时候,显然,我们应该把 \(l_{i,j}=r_{i,j}=j\),因为最开始的时候肯定都是可以到自己这里来的,同样的 \(u_{i,j}=1\)

for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(),l[i][j]=r[i][j]=j,u[i][j]=1;

之后我们来更新 \(l_{i,j}\)\(r_{i,j}\)

想一下,从 \(i,j\) 开始横着枚举,只要 \(a_{i,j-1}\ xor\ a_{i,j}\),那么我们的 \(l_{i,j}\) 就可以向左增加一, \(r\) 同理。

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 j=m-1;j>=1;j--) if(a[i][j]!=a[i][j+1]) r[i][j]=r[i][j+1];
}

最后的更新部分是 \(u\)。事实上,只要我上面这个点和我当前的点不一样,就可以向上延伸,但是要注意的是,延伸之后,\(l\)\(r\) 要在 \((i-1,j)\)\((i,j)\) 之间取个 \(min\).

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++) 
    {
        if(i>1 && a[i][j]!=a[i-1][j])
        {
            u[i][j]=u[i-1][j]+1;
            Max(l[i][j],l[i-1][j]),Min(r[i][j],r[i-1][j]);
        }
    }
}

现在已经更新完了,我们是时候统计答案了。

想一下,对于每个点,正方形肯定就是他的 \(r-l+1\)\(u\) 的值取min作为边长,矩形乘起来即可。

#include<bits/stdc++.h>
#define Max(x,y) x=max(x,y)
#define Min(x,y) x=min(x,y)
using namespace std;
const int N=2010;
int l[N][N],r[N][N],u[N][N];
int n,m,a[N][N];
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(),l[i][j]=r[i][j]=j,u[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 j=m-1;j>=1;j--) if(a[i][j]!=a[i][j+1]) r[i][j]=r[i][j+1];
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(i>1 && a[i][j]!=a[i-1][j]) u[i][j]=u[i-1][j]+1,Max(l[i][j],l[i-1][j]),Min(r[i][j],r[i-1][j]);
//	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cout<<l[i][j]<<" "<<r[i][j]<<endl;
	int ans1=0,ans2=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int len=r[i][j]-l[i][j]+1,h=u[i][j];
			Max(ans1,min(len,h)*min(len,h));
			Max(ans2,len*h);
		}
	}
	cout<<ans1<<"\n"<<ans2<<endl;
	return 0;
}

版权声明
本文为[Dijkstra6627]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/juruo-wsy/p/15114299.html