[luogu1034] 矩形覆盖 (暴力)

Description

给n(n<=50)个点(x,y)，要求用k(1<=k<=4)个没有联系的矩形覆盖住求矩形最小面积

Solution

感觉不是很可做，结果看TJ后发现数据太水直接暴力233

Code

//By Menteur_Hxy

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

using namespace std;

inline int read() {

	int x=0,f=1; char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=60,INF=0x3f3f3f3f;

int n,k,ans;

int col[N],l[5],r[5],u[5],d[5],da[5];

struct Poi{int x,y;}p[N];

inline int get(int x) {

	int res=0;

	F(i,1,k) l[i]=u[i]=INF,r[i]=d[i]=da[i]=0;

	F(i,1,x) {

		int c=col[i];

		l[c]=min(l[c],p[i].y); u[c]=min(u[c],p[i].x);

		r[c]=max(r[c],p[i].y); d[c]=max(d[c],p[i].x);

		da[c]=(r[c]-l[c])*(d[c]-u[c]);

	}

	F(i,1,k) res+=da[i];

	return res;

}

inline void dfs(int x) {

	if(x==n+1) {

		int res=get(n);

		F(i,1,n) F(j,1,k) if(col[i]!=j)

			if(l[j]<=p[i].y&&p[i].y<=r[j]&&

			u[j]<=p[i].x&&p[i].x<=d[j]) return ;

		ans=min(ans,res);

		return ;

	}

	F(i,1,k) {

		col[x]=i;

		if(get(x)>ans) continue;

//		printf("%d %d %d %d %d\n",x,l[i],r[i],u[i],d[i]);

		dfs(x+1);

		col[x]=0;

	}

	return ;

}

int main() {

	n=read(),k=read();

	F(i,1,n) p[i].x=read(),p[i].y=read();

	ans=INF; dfs(1);

	printf("%d",ans);

	return 0;

}

巴特西

[luogu1034] 矩形覆盖 (暴力)

Description

Solution

Code

最新文章

热门文章