P1578 奶牛浴場 懸線法+dp

原題:https://www.luogu.org/problemnew/show/P1578

題解:給一些障礙物，求最大矩形的面積，不能覆寫障礙物。懸線概念：

有效豎線：除了兩個端點外，不覆寫任何障礙點的豎直線段。 懸線：上端點覆寫了一個障礙點或達到整個矩形上端的有效豎線。

每個懸線都與它底部的點一 一對應。每個懸線可以向左右擴充就會得到一個矩形。最大矩形一定在這些矩形中。設：

h[i][j] 為點(i,j)懸線的長度
l[i][j] 為點(i,j)懸線向左最遠能達到的位置
r[i][j] 為點(i,j)懸線向右最遠能達到的位置
           

考慮狀态轉移

如果(i-1,j)是障礙點。(i,j)對應的懸線長度1，左右能移動到的位置是整個矩形的左右邊界。

如果不是。懸線長應該是h[i-1][j]+1。左端點應該是 max{l[i-1][j] ,(i-1,j)左邊最近的障礙點 }右端點應是min{r[i-1][j],右邊最近的障礙物}

細節:

1.當長寬很大時要離散化。

2.沒有把上下邊界形成的矩形算上，要進行特判。

3.本題遞推時要用滾動數組，并且表示位置的數組要用short,不然mle

4.tag數組最外一圈是邊界，離散化是坐标要+1

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=5005;
int x[N],y[N],sx[N],sy[N];
short pre[N][N],nxt[N][N];
short h[2][N],l[2][N],r[2][N];
bool tag[N][N];
int xcnt,ycnt,n,ans;
inline int rd(){
	int x=0;int f=1;char s=getchar();
	while(!isdigit(s)){if(s=='-')f=-1;	s=getchar();}
	while(isdigit(s)) x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return x*f; 
}
int main(){
//	freopen("testdata.in","r",stdin);	
	sx[++xcnt]=0;sx[++xcnt]=rd();
	sy[++ycnt]=0;sy[++ycnt]=rd();
	n=rd();
	for(int i=1;i<=n;i++){
		x[i]=rd();y[i]=rd();
		sx[++xcnt]=x[i];
		sy[++ycnt]=y[i]; 
	}
	sort(sx+1,sx+xcnt+1);xcnt=unique(sx+1,sx+xcnt+1)-(sx+1);
	sort(sy+1,sy+ycnt+1);ycnt=unique(sy+1,sy+ycnt+1)-(sy+1);
	
	ans=0;
	//特判 和上下邊界的矩型 
	for(int j=2;j<=ycnt;j++) ans=max(ans,(sy[j]-sy[j-1])*sx[xcnt]);
	
	for(int i=1;i<=n;i++){
		x[i]=lower_bound(sx+1,sx+xcnt+1,x[i])-sx; // tag[1][]為邊界 
		y[i]=lower_bound(sy+1,sy+ycnt+1,y[i])-sy;
		tag[x[i]][y[i]]=1;
	} 
	for(int i=1;i<=xcnt;i++) tag[i][1]=tag[i][ycnt]=1;
	for(int j=1;j<=ycnt;j++) tag[1][j]=tag[xcnt][j]=1;
	
	for(int i=1;i<=xcnt;i++){
		int last=1;
		for(int j=2;j<=ycnt;j++) {
			if(!tag[i][j]) continue;
			for(int k=last+1;k<j;k++) nxt[i][k]=j;
			for(int k=last+1;k<j;k++) pre[i][k]=last; 
			last=j;
		}
	}
	int t=1;
	for(int j=1;j<=ycnt;j++) l[t][j]=1,r[t][j]=ycnt;
	t^=1; 
	for(int i=2;i<=xcnt;i++,t^=1){
		for(int j=1;j<=ycnt;j++){
			if(tag[i-1][j]){
				h[t][j]=1; 
				l[t][j]=1; 
				r[t][j]=ycnt;
			}else{
				h[t][j]=h[t^1][j]+1;
				l[t][j]=max(l[t^1][j],pre[i-1][j]);
				r[t][j]=min(r[t^1][j],nxt[i-1][j]);
			}
			ans=max(ans,(sx[i]-sx[i-h[t][j]])*(sy[r[t][j]]-sy[l[t][j]]));
		}
	} 
	printf("%d\n",ans); 
	return 0;
}