NOIP2002矩形覆盖
题目描述 Description
在平面上有 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。各个矩形必须完全分开（边线与顶点也都不能重合）。
输入描述 Input Description
n k
xl y1x2 y2
… …
xn yn （0<=xi,yi<=500)
输出描述 Output Description
一个整数，即满足条件的最小的矩形面积之和。
样例输入 Sample Input
4 2
1 1
2 2
3 6
0 7
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
k<4
官方是k<=4，但是标程解法在k=4时是有反例的。官方的数据也没有出现k=4的情况
代码
乍一看好像是对的，不过是有反例的，但是由于数据太水，你懂得
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; struct data{ int x,y; }a[51]; int n,k,l,r; int f[51][51][4]; inline bool cmp(data a,data b) { if(a.y==b.y)return a.x<b.x; return a.y<b.y; } int main() { memset(f,127/3,sizeof(f)); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { l=r=a[i].x; for(int j=i;j<=n;j++) { l=min(l,a[j].x);r=max(r,a[j].x); f[i][j][1]=(a[j].y-a[i].y)*(r-l); } } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) for(int q=i;q<j;q++) { f[i][j][2]=min(f[i][q][1]+f[q+1][j][1],f[i][j][2]); } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) for(int q=i;q<j;q++) { f[i][j][3]=min(f[i][q][1]+f[q+1][j][2],f[i][j][3]); f[i][j][3]=min(f[i][q][2]+f[q+1][j][1],f[i][j][3]); } printf("%d",f[1][n][k]); return 0; } |
还可以按x,y进行排序后做俩次取最小值。。。。我无法证明其正确性，这算高级骗分么。。
还是搜索比较保险
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; struct data1{ int x,y; }p[51]; struct data2 { int l,r,u,d; bool flag; }re[5]; int n,m,ans=0x7fffffff; bool in(data2 a,int xx,int yy) { if(xx>=a.l&&xx<=a.r&&yy>=a.d&&yy<=a.u)return 1; return 0; } bool coin(data2 a,data2 b) { if(in(b,a.l,a.d))return 1; if(in(b,a.l,a.u))return 1; if(in(b,a.r,a.d))return 1; if(in(b,a.r,a.u))return 1; return 0; } void dfs(int k) { int i,j,s=0;data2 tmp; for(i=1;i<=m;i++) if(re[i].flag) { s+=(re[i].r-re[i].l)*(re[i].u-re[i].d); for(j=i+1;j<=m;j++) if(re[j].flag&&coin(re[i],re[j]))return; } if(s>=ans)return; if(k>n){ans=s;return;} for(i=1;i<=m;i++) { tmp=re[i]; if(!re[i].flag) { re[i].l=p[k].x;re[i].r=p[k].x; re[i].u=p[k].y;re[i].d=p[k].y; re[i].flag=1; } else { re[i].l=min(re[i].l,p[k].x);re[i].r=max(re[i].r,p[k].x); re[i].d=min(re[i].d,p[k].y);re[i].u=max(re[i].u,p[k].y); } dfs(k+1); re[i]=tmp; } } int main() { int i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y); dfs(1); printf("%d",ans); return 0; } |
计数器 9734136
OI 课件=>
OI 课件=>
博主您好，今天下午调试此题时我用您dfs版本的代码对拍时发现始终拍不上，经过仔细研究后发现您的代码中判断两个矩形是否重叠的方法有些bug，具体来讲就是当两个矩形呈十字形交叉时，两矩形重叠，而A矩形的任何一个顶点均不在B矩形内部，您的
coin()函数对此反例会产生误判。hack数据如下：4 27 4
5 5
3 4
4 2
标准输出：
4如果点的数量是50，，，那么就会超时，，，博主的代码是跟点的个数相关的。。。
本人苟蒻。。。。借博主代码一测，，结果超时。。。