首页 > 代码库 > Vijos1055 奶牛浴场(极大化思想求最大子矩形)

Vijos1055 奶牛浴场(极大化思想求最大子矩形)

思路详见 王知昆《浅谈用极大化思想解决最大子矩形问题》

写得很详细(感谢~....)

因为不太会用递推,所以用了第一种方法,时间复杂度是O(n^2),n为枚举的点数,对付这题绰绰有余

 

思路也很简单

先根据x排序

之后两重循环,枚举i后的每一个点j到i可以形成的矩形面积

怎么求这个矩形面积呢?

非常简单,miny,maxy,分别表示纵坐标的上下界

如果枚举的点j比i的y大,那么就修改上界,反之,修改下界(具体的,可以看论文中的图,更直观些)

 

这里需要注意两个遗漏的地方(论文中也有特别提到)

就是子矩形左右边界是否与大矩形有重合的问题

 

由于我写的代码,是在算完i到j的矩形面积之后,再更新上下界的

所以,在第二重循环结束之后,在算一次:s=(lx-x)*(maxy-miny)即可

这是从左到右枚举的情况(可解决右边界重合)

 

同理,再从右到左枚举一遍,即可解决左边界重合的情况

(mark:我并没有解决,左右边界同时重合的情况,但是还是A了...数据太弱?)

 

附上代码:

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int lx,ly,n,s,maxs=0;struct node{	int x,y;}f[5001];bool cmp(const node &a,const node &b){//按照x排序,其次按y排序(其实与y如何排序没有太大关系	if(a.x<b.x) return 1;	else if(a.x==b.x && a.y>b.y) return 1;	else return 0;}int main(){	//freopen("data.txt","r",stdin);	scanf("%d%d",&lx,&ly);	scanf("%d",&n);	if(n==0){//特判		cout<<lx*ly;		return 0;	}	for(int i=1;i<=n;i++){		scanf("%d%d",&f[i].x,&f[i].y);	}	sort(f+1,f+n+1,cmp);	int dx,dy;	for(int i=1;i<=n;i++){//从左到右枚举		s=0;		int miny=0,maxy=ly;//上下界初始化		for(int j=i+1;j<=n;j++){			dx=f[j].x-f[i].x;			dy=maxy-miny;			s=dx*dy;			if(s>maxs) maxs=s;//根据论文中的图解模拟即可,需要在算完S之后更新上下界			if(f[j].y>=f[i].y && f[j].y<maxy) maxy=f[j].y;			if(f[j].y<=f[i].y && f[j].y>miny) miny=f[j].y;		}		dx=lx-f[i].x;		dy=maxy-miny;//由于已更新了最后扫到的点,最后不需要再更新		s=dx*dy;		if(s>maxs) maxs=s;	}	for(int i=n;i>=1;i--){//从右到左枚举同上思路(其实可以写一个函数减少代码量QAQ)		s=0;		int miny=0,maxy=ly;		for(int j=i-1;j>=1;j--){			dx=f[i].x-f[j].x;			dy=maxy-miny;			s=dx*dy;			if(s>maxs) maxs=s;			if(f[j].y>=f[i].y && f[j].y<maxy) maxy=f[j].y;			if(f[j].y<=f[i].y && f[j].y>miny) miny=f[j].y;		}		dx=f[i].x-0;		dy=maxy-miny;		s=dx*dy;		if(s>maxs) maxs=s;	}	cout<<maxs;	return 0;}

 

Vijos1055 奶牛浴场(极大化思想求最大子矩形)