NOIP 2002 矩形覆盖

佚名 6年前 (2019-04-19) 随笔 1179人围观抢沙发百度已收录

当年的一道D2T1，一眼看上去很简单的样子，但是实际做起来没那么容易。

看一眼数据范围，很好可以考虑搜索，首先想到的是搜什么。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

如果从矩形开始搜，虽然至多只有4个矩形，但是可以有很多很多很多种的组合。因为一个矩形要么由对角线上顶点确定，要么由一个顶点与不包含该顶点的两边上的各一点确定，这样搜索会有2500^4种情况显然会炸。

那么考虑从点开始搜，点能怎么搜呢？依次考虑能把它放到哪个矩形中即可。实现时用一个结构体存储矩形（最多就四个），每个点依次放入不同矩形，同时维护放入矩形的边界然后搜下一个点，如果搜到一个矩形发现它还没有被使用，就把它的边界全部设为点的坐标来构建一个新矩形。加上一个剪枝快到飞起。

呆马：

#include<cstdio> #include<algorithm>
using namespace std; int n,m,ans=0x7f7f7f7f; struct node { int x,y; }dot[60]; struct martix { int l,r,f,t; bool flag; }jz[5]; bool in(martix k,int x,int y) { if(x<=k.r&&x>=k.l&&y<=k.f&&y>=k.t) return 1; return 0; } bool judge(martix k,martix m) { if(in(k,m.l,m.f)) return 0; if(in(k,m.r,m.f)) return 0; if(in(k,m.l,m.t)) return 0; if(in(k,m.r,m.t)) return 0; return 1; } void dfs(int sum) { int val=0; for(int i=1;i<=m;i++) { if(jz[i].flag) { for(int j=i+1;j<=m;j++) if(!judge(jz[i],jz[j])) return; } val+=(jz[i].r-jz[i].l)*(jz[i].f-jz[i].t); } if(val>=ans) return; if(sum>n) { ans=val; return; } for(int i=1;i<=m;i++) { martix tmp=jz[i]; if(!jz[i].flag) { jz[i].flag=1; jz[i].l=jz[i].r=dot[sum].x; jz[i].f=jz[i].t=dot[sum].y; dfs(sum+1); jz[i]=tmp; break; } else { jz[i].l=min(jz[i].l,dot[sum].x); jz[i].r=max(jz[i].r,dot[sum].x); jz[i].f=max(jz[i].f,dot[sum].y); jz[i].t=min(jz[i].t,dot[sum].y); dfs(sum+1); jz[i]=tmp; } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d",&dot[i].x,&dot[i].y); dfs(1); printf("%d",ans); return 0; }