题解 P1034 【矩形覆盖】
ShineEternal
2019-08-29 21:03:57
## 题目链接:
https://www.luogu.org/problem/P1034
这道题调了半天,纪念一下。
## 分析:
**搜索**。
~~总结一下其实发现早些年搜索题目挺多,主要是因为评测机不发达只能手工读入之类而能在工作人员承受之内的大概就是搜索极高的一般非正解的时间复杂度从而得到较小的数据~~
从第一个点往最后搜,在搜索中都有以下可以进入下一个分支的:
- 当前点包含在一个矩形内
- 当前点由一个矩形扩展过来
- 当前点自成一个矩形
**注意三条都要进行,因为题目说必须要弄出k个矩形,所以不存在搜索中贪心的相关思想**
## $code:$
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
struct ben
{
int x1,y1,x2,y2;//记录矩形的左下角和右上角
}jx[10];
int ans=2147483647;
int n,k;
int x[55],y[55];
int check(int x,int cnt)//判断第x个矩形与其他是否重,=0有重,四种重复情况
{
for(int i=1;i<=cnt;i++)
{
if(i!=x)
{
if(jx[i].x1<=jx[x].x1&&jx[i].x2>=jx[x].x1&&jx[i].y1<=jx[x].y1&&jx[i].y2>=jx[x].y1)
return 0;
if(jx[i].x2<=jx[x].x2&&jx[i].x2>=jx[x].x2&&jx[i].x2<=jx[x].y2&&jx[i].x2>=jx[x].y2)
return 0;
if(jx[i].y1<=jx[x].y1&&jx[i].y2>=jx[x].y1&&jx[i].x2<=jx[x].x2&&jx[i].x2>=jx[x].x2)
return 0;
if(jx[i].y1<=jx[x].y2&&jx[i].y2>=jx[x].y2&&jx[i].x2<=jx[x].x1&&jx[i].x2>=jx[x].x1)
return 0;
}
}
return 1;
}
int mj(int i)//矩形面积
{
return (jx[i].x2-jx[i].x1)*(jx[i].y2-jx[i].y1);
}
void dfs(int now,int s,int cnt)
{
if(s>ans)return ;
if(now==n+1)
{
//printf("%d\n",s);
if(cnt==k)
ans=min(ans,s);
return ;
}
for(int i=1;i<=cnt;i++)//判断能不能放在之前的
{
if(jx[i].x1<=x[now]&&jx[i].x2>=x[now]&&jx[i].y1<=y[now]&&jx[i].y2>=y[now]) //now是否包含在第i个矩形里
{
dfs(now+1,s,cnt);
}
else
{
int tmp1,tmp2,tmp3,tmp4;
tmp1=jx[i].x1;
tmp2=jx[i].x2;
tmp3=jx[i].y1;
tmp4=jx[i].y2;
int stmpf=mj(i);
if(x[now]<jx[i].x1)
{
jx[i].x1=x[now];
}
else
if(x[now]>jx[i].x2)
{
jx[i].x2=x[now];
}
if(y[now]<jx[i].y1)
{
jx[i].y1=y[now];
}
else
if(y[now]>jx[i].y2)
{
jx[i].y2=y[now];
}
int stmp=mj(i);
if(check(i,cnt))
dfs(now+1,s+stmp-stmpf,cnt);//扩大一个矩形
jx[i].x1=tmp1;
jx[i].x2=tmp2;
jx[i].y1=tmp3;
jx[i].y2=tmp4;
}
}
//if(flag==1)return ;
if(cnt==k)return ;
cnt++;
jx[cnt].x1=x[now];
jx[cnt].x2=x[now];
jx[cnt].y1=y[now];
jx[cnt].y2=y[now];
dfs(now+1,s,cnt);//新增一个矩形
jx[cnt].x1=0;
jx[cnt].x2=0;
jx[cnt].y1=0;
jx[cnt].y2=0;
cnt--;
return;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
dfs(1,0,0);
printf("%d\n",ans);
return 0;
}
```