洛谷P1034 矩形覆盖
2020-03-10 16:01:15来源:博客园 阅读 ()
洛谷P1034 矩形覆盖
P1034 矩形覆盖
题目描述
在平面上有n个点(n<=50),每个点用一对整数坐标表示。例如:当n=4时,4个点的坐标分另为:p1(1,1),p2(2,2),p3(3,6),P4(0,7),见图一。
这些点可以用 k 个矩形(1<=k<=4)全部覆盖,矩形的边平行于坐标轴。当 k=2 时,可用如图二的两个矩形 sl,s2 覆盖,s1,s2 面积和为 4。问题是当 n 个点坐标和 k 给出后,怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定:覆盖一个点的矩形面积为 0;覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开(边线与顶点也都不能重合)。
输入格式
n k
xl y1
x2 y2
… …
xn yn
(0<=xi,yi<=500)
输出格式
输出至屏幕。格式为:
一个整数,即满足条件的最小的矩形面积之和。
输入输出样例
输入
4 2
1 1
2 2
3 6
0 7
输出
4
分析
主要是搜索。
这题剪枝方法似乎多种多样。
下面将要展示代码的做法:
将读入的坐标按x和y从小到大排序,然后搜索将连续的i个点分在一起,期间判断问题是否可行,以及进行各种小优化。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct point{
int x,y;
}a[60];
int cmp(point a,point b){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
struct block{
int x1,y1,x2,y2;
}b[5];
int n,k;
int ans=1e9;
void DFS(int pos,int cnt,int smm){
if(pos>n){
ans=min(ans,smm);
return;
}
if(cnt>k)return;
int i,j;
b[cnt].x1=a[pos].x;
b[cnt].x2=a[pos].x;
b[cnt].y1=a[pos].y;
b[cnt].y2=a[pos].y;
for(i=pos;i<=n;i++){
b[cnt].y2=max(b[cnt].y2,a[i].y);
b[cnt].x2=max(b[cnt].x2,a[i].x);
b[cnt].x1=min(b[cnt].x1,a[i].x);
b[cnt].y1=min(b[cnt].y1,a[i].y);
for(j=1;j<cnt;j++){
if(b[cnt].x1<=b[j].x2 && b[cnt].y1<=b[j].y2)return;
}
if(i<n && cnt==k)continue;
DFS(i+1,cnt+1,smm+(b[cnt].x2-b[cnt].x1)*(b[cnt].y2-b[cnt].y1));
}
return;
}
int main(){
n=read();k=read();
int i,j;
for(i=1;i<=n;i++){
a[i].y=read();a[i].x=read();
}
sort(a+1,a+n+1,cmp);
memset(b,-1,sizeof b);
DFS(1,1,0);
printf("%d\n",ans);
return 0;
}
原文链接:https://www.cnblogs.com/jiupinzhimaguan/p/12452766.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1014 Cantor表 2020-02-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash