悬线法

悬线法可以理解为是一种dp .

资料介绍

https://wenku.baidu.com/view/cd82b3f5e87101f69f3195bc.html

上述资料其实介绍了两种算法.

算法1适用于 点数较小时.

算法2适用于$ n*m$ 较小时,算法2更普遍的被叫做 悬线法.

上述两种算法各有各自的适用范围.

zjoi2007 棋盘制作

题目链接: https://www.luogu.com.cn/problem/P1169
参考资料: https://zhuanlan.zhihu.com/p/46382722

使用 悬线法(算法2) 的ac代码

#include <bits/stdc++.h>
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}




const int maxv=4e3+10;
int n,m,ans1,ans2;

#define l left
#define r right
#define h height

int res[maxv][maxv];
int l[maxv][maxv];
int r[maxv][maxv];
int h[maxv][maxv];


int main(){

	scanf("%d%d",&n,&m);
	inc(i,1,n) inc(j,1,m) {
		scanf("%d",&res[i][j]);
		l[i][j]=r[i][j]=j;
		h[i][j]=1;

	}
	// h[i][j] 表示点(i,j)对应的悬线的长度
	// l[i][j] 表示点(i,j)对应的悬线向左能够移动到的位置
	// r[i][j] 表示点(i,j)对应的悬线向右能够移动到的位置
	inc(i,1,n) inc(j,2,m) 
		if(res[i][j]!=res[i][j-1]) left[i][j]=left[i][j-1];
	inc(i,1,n) dec(j,m-1,1) 
		if(res[i][j]!=res[i][j+1]) right[i][j]=right[i][j+1];
	inc(i,1,n) inc(j,1,m) {
		if(i>1 && res[i][j]!=res[i-1][j]) {
			left[i][j]=std::max(left[i][j],left[i-1][j]);
			right[i][j]=std::min(right[i][j],right[i-1][j]);
			height[i][j]=height[i-1][j]+1;
		}
		int a=right[i][j]-left[i][j]+1;
		int b=std::min(a,height[i][j]);


		ans1=std::max(ans1,b*b);
		ans2=std::max(ans2,a*height[i][j]);
	}
	printf("%d\n%d\n",ans1,ans2);
	return 0;
}

使用单调栈的ac代码

// ac
// 利用单调栈通过了该题目
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


const int maxv=2e3+10;
int val[maxv];
int st[maxv];
int s,t;
int l[maxv],r[maxv];

int a[maxv][maxv];

int n,m;
int main(){
	while(~scanf("%d%d",&n,&m)){
		inc(i,1,n) inc(j,1,m){
			scanf("%d",&a[i][j]);
			if((i+j)%2==0) a[i][j]^=1;
		}

		inc(i,1,m) val[i]=0;
		int ans1=0;
		int ans2=0;
		inc(i,1,n) {
			inc(j,1,m) 
				if(a[i][j]==0) val[j]++;
				else if(a[i][j]==1) val[j]=0;
			s=t=0;
			inc(k,1,m){
				int now = val[k];
				while(s<t && val[st[t-1]]>=now) t--;
				if(s==t) l[k]=1;
				else l[k]=st[t-1]+1;
				st[t++]=k;
			}
			s=t=0;
			dec(k,m,1){
				int now = val[k];
				while(s<t && val[st[t-1]]>=now) t--;
				if(s==t) r[k]=m;
				else r[k]=st[t-1]-1;
				st[t++]=k;
			}
			inc(k,1,m){
				int a=r[k]-l[k]+1;
				int b=val[k];
				int c=min(a,b);
				ans1=max(ans1,c*c);
				ans2=max(ans2,a*b);
			}
		}
		inc(i,1,m) val[i]=0;
		inc(i,1,n) {
			inc(j,1,m) 
				if(a[i][j]==1) val[j]++;
				else if(a[i][j]==0) val[j]=0;
			s=t=0;
			inc(k,1,m){
				int now = val[k];
				while(s<t && val[st[t-1]]>=now) t--;
				if(s==t) l[k]=1;
				else l[k]=st[t-1]+1;
				st[t++]=k;
			}
			s=t=0;
			dec(k,m,1){
				int now = val[k];
				while(s<t && val[st[t-1]]>=now) t--;
				if(s==t) r[k]=m;
				else r[k]=st[t-1]-1;
				st[t++]=k;
			}

			inc(k,1,m){
				int a=r[k]-l[k]+1;
				int b=val[k];
				
				int c=min(a,b);

				ans1=max(ans1,c*c);
				ans2=max(ans2,a*b);
			}
		}


		cout<<ans1<<"\n"<<ans2<<"\n";
	}
	return 0;
}

[USACO5.3]巨大的牛棚

题目链接 https://www.luogu.com.cn/problem/P2701

参考资料 https://www.cnblogs.com/liweihang/p/13489910.html

其实转化一下就是01矩阵中求全0的正方形矩阵最大的边长.

悬线法ac的代码

//ac
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


int n,t;
const int maxv=1e3+10;
int a[maxv][maxv];
int l[maxv][maxv];
int r[maxv][maxv];
int h[maxv][maxv];
int ans;


int main(){

	while(~scanf("%d%d",&n,&t)){
		inc(i,1,n) inc(j,1,n) a[i][j]=0;
		while(t--){
			int tx,ty;scanf("%d%d",&tx,&ty);
			a[tx][ty]=1;
		}
		
		/*
		inc(i,1,n){
			inc(j,1,n) printf("%4d",a[i][j]);
			printf("\n");
		}
		*/

		inc(i,1,n) inc(j,1,n){
			l[i][j]=r[i][j]=j;
			h[i][j]=1;
		}

		ans=0;
		inc(i,1,n) inc(j,2,n) 
			if(a[i][j-1]==0 && a[i][j]==0)
				l[i][j]=l[i][j-1];
		inc(i,1,n) dec(j,n-1,1)
			if(a[i][j]==0 && a[i][j+1]==0)
				r[i][j]=r[i][j+1];

		inc(i,1,n) inc(j,1,n){
			if(i>1 && a[i][j]==0 && a[i-1][j]==0){
				l[i][j]=max(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
				h[i][j]=h[i-1][j]+1;
			}

			int aa=r[i][j]-l[i][j]+1;

			int bb=h[i][j];

			int c=min(aa,bb);
			ans=max(ans,c);

		}
		printf("%d\n",ans);
	}
	return 0;
}

单调栈ac的代码

// queue
// ac
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


int n,m,T;
const int maxv=1e3+10;
int a[maxv][maxv];

int val[maxv];
int st[maxv];
int l[maxv],r[maxv];

int ans;
int s,t;

int main(){
	while(~scanf("%d%d",&n,&T)){
		m=n;
		inc(i,1,n) inc(j,1,m) a[i][j]=0;
		while(T--){
			int tx,ty;scanf("%d%d",&tx,&ty);
			a[tx][ty]=1;
		}
		ans=0;
		inc(i,1,m) val[i]=0;

		inc(i,1,n){
			inc(j,1,m) 
				if(a[i][j]==0) val[j]++;
				else val[j]=0;

			s=t=0;

			inc(j,1,m){
				while(s<t && val[st[t-1]]>= val[j]) t--;
				if(s==t) l[j]=1;
				else l[j]=st[t-1]+1;
				st[t++]=j;
			}

			s=t=0;
			dec(j,m,1){
				while(s<t && val[st[t-1]]>= val[j]) t--;
				if(s==t) r[j]=m;
				else r[j]=st[t-1]-1;
				st[t++]=j;
			}

			inc(j,1,m){

				int alpha=r[j]-l[j]+1;
				int beta=val[j];
				ans=max(ans,min(alpha,beta));
			}

//			inc(j,1,m) printf("%4d",l[j]);cout<<endl;
//			inc(j,1,m) printf("%4d",r[j]);cout<<endl;
		}
		printf("%d\n",ans);
	}
	return 0;
}

奶牛浴场

题目链接 https://www.luogu.com.cn/problem/P1578

参考资料 https://www.pianshen.com/article/1245215508/

这个题目是因为 $ n$和 $m $ 较大,所以使用了算法1,时间复杂度是o($s^2$)

在具体处理时,有一些特殊情况的处理,具体细节见代码 : - 0

ac代码

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

#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


#define node point 

struct point{ 
	ll x,y; 
	point(ll x=0,ll y=0):x(x),y(y){}
}a[5010];

int main(){
	ll L,W;scanf("%lld%lld",&L,&W);
	int n;scanf("%d",&n);
	inc(i,1,n) scanf("%lld%lld",&a[i].x,&a[i].y);
	a[++n]=point(0,0);
	a[++n]=point(0,W);
	a[++n]=point(L,0);
	a[++n]=point(L,W);
	sort(a+1,a+n+1,[](const node & a, const node & b){
			return (a.x==b.x)? a.y<b.y: a.x<b.x;
			});
	ll ans=0;

	for(int i=1;i<=n;i++){
		ll l=0,h=W,v=L-a[i].x;
		for(int j=i+1;j<=n;j++){
			if(a[j].y<=h && a[j].y>=l || a[j].x==L){


				if(v*(h-l)<=ans) break;
				ans=max(ans,(h-l)*(a[j].x-a[i].x));
				if(a[j].y==a[i].y) break;
				if(a[j].y>a[i].y) h=min(h,a[j].y);
				else l=max(l,a[j].y);
			}
		}
		l=0,h=W,v=a[i].x;
		for(int j=i-1;j>=1;j--){
			if((a[j].y<=h && a[j].y>=l) || a[j].x==0){
				if(v*(h-l)<=ans)  break;
				ans=max(ans,(h-l)*(a[i].x-a[j].x));
				if(a[j].y==a[i].y) break;
				if(a[j].y>a[i].y) h=min(h,a[j].y);
				else l=max(l,a[j].y);
			}
		}
	}

	sort(a+1,a+1+n,[](node &a,node &b){
			return a.y<b.y;
			});
	inc(i,1,n-1)
		ans=max(ans,(a[i+1].y-a[i].y)*L);
	printf("%lld\n",ans);
	return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!