洛谷P1034 矩形覆盖

0
9

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;
}

题目跳转 | 提交入口

<

发布回复

请输入评论!
请输入你的名字