好吧 我是伞兵
当前面积>目前最优答案要剪枝
改完瞬间TLE->19ms
封贴QWQ(所以为什么题解说不要剪枝)
警钟长鸣~~~
by 137QWQ @ 2022-10-01 22:01:39
%%%
by xyzlh @ 2022-10-02 11:27:28
我来
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k;
int xx[505],yy[505];
int x,y;
struct b{
int f;
int t;
double l;
} ed[2500];
int fa[100001];
int bl[2500];
struct re{
int lx,rx,uy,dy;
}rec[2500];
re tem;
re recc[5];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int f(int x){
return x*x;
}
int di(int x,int y){
return f(xx[x]-xx[y])+f(yy[x]-yy[y]);
}
bool cmp(b x,b y){
return x.l<y.l;
}
int p;
void add(int f,int to,int ne){
ed[++p].f=f;
ed[p].t=to;
ed[p].l=ne;
return ;
}
int cnt;
void com(int x,int y){
recc[y].lx=min(recc[y].lx,rec[x].lx);
recc[y].uy=min(recc[y].uy,rec[x].uy);
recc[y].rx=max(recc[y].rx,rec[x].rx);
recc[y].dy=max(recc[y].dy,rec[x].dy);
}
void can(int x,int y,re tem){
//cnt--;
recc[y]=tem;
}
int Aimee;
int znx=0x3fffff;
int ss(){
Aimee=0;
for(int i=1;i<=cnt;++i){
Aimee+=(recc[i].rx-recc[i].lx)*(recc[i].dy-recc[i].uy);
}
return Aimee;
}
void endd(){
Aimee=0;
for(int i=1;i<=cnt;++i){
Aimee+=(recc[i].rx-recc[i].lx)*(recc[i].dy-recc[i].uy);
}
znx=min(znx,Aimee);
}
bool ch(int i,int xx,int yy){
return (xx<=recc[i].rx&&xx>=recc[i].lx&&recc[i].dy>=yy&&recc[i].uy<=yy);
}
bool che(int x,int xx,int yy){
for(int i=1;i<=cnt;++i){
if(i==x)
continue;
if(ch(x,recc[i].lx,recc[i].dy)||
ch(x,recc[i].lx,recc[i].uy)||
ch(x,recc[i].rx,recc[i].dy)||
ch(x,recc[i].rx,recc[i].uy))
return 0;
}
return 1;
}
void kr(int i,int s){
if(s>znx){
return ;
}
if(i==n+1){
if(cnt==k)
znx=s;
return ;
}
if(cnt<k){
re tem=recc[cnt+1];
cnt++;
recc[cnt]=rec[i];
if(che(cnt,rec[i].lx,rec[i].dy))
kr(i+1,ss());
recc[cnt]=tem;
cnt--;
}
for(int j=1;j<=cnt;++j){
re tem=recc[j];
com(i,j);
if(che(j,rec[i].lx,rec[i].dy))
kr(i+1,ss());
can(i,j,tem);
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i){
scanf("%d%d",&x,&y);
rec[i].lx=rec[i].rx=x;
rec[i].dy=rec[i].uy=y;
}
kr(1,0);
cout<<znx;
return 0;
}
```
这下就好了
by www101 @ 2023-03-03 15:49:02