P1034 矩形覆盖
题目描述
在平面上有 (n) 个点（(n leq 50)），每个点用一对整数坐标表示。例如：当 (n＝4) 时，4个点的坐标分另为：(p_1(1,1))，(p_2(2,2))，(p_3(3,6))，(p_4(0,7))，见图一。
这些点可以用 (k) 个矩形（(1 leq k leq 4)）全部覆盖，矩形的边平行于坐标轴。当 (k=2) 时，可用如图二的两个矩形 (s_1，s_2) 覆盖，(s_1)，(s_2) 面积和为 (4)。问题是当 (n) 个点坐标和 (k) 给出后，怎样才能使得覆盖所有点的 (k) 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 (0)；覆盖平行于坐标轴直线上点的矩形面积也为 (0)。各个矩形必须完全分开（边线与顶点也都不能重合）。
输入格式
(n k)
(x_1 y_1)
(x_2 y_2)
… …
(x_n y_n)((0 leq x_i,y_i leq 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
",ans);
return 0;
}