p2831——愤怒的小鸟

这题不就是暴力枚举吗，dfs爆搜就行，记一下前面有几条抛物线了，有几个单着的猪，分三种情况，如果来了一个新猪，满足前面的其中一条抛物线，那么直接向下搜即可（这样最优）；新猪和以前单着的猪凑成一条抛物线；此猪作为一个单猪存在。 ~~（算抛物线的a，b时，推式子推到**）~~ ```cpp // luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<map> #include<set> #define ri register int #define max maxx #define min minn using namespace std; const double eps=1e-8; inline int maxx(int x,int y) { return x>y?x:y; } inline int minn(int x,int y) { return x<y?x:y; } struct node { double x,y; } a[250],single_pig[250]; struct NODE { double a,b; } par[250]; int t,n,m,ans,tim; double k,kk,t1,t2,tmp,temp; bool flag; /*inline bool fuc(int tn,int tm,double &tmp,double &temp) { //a[t1].x*a[t1].x*k+a[t1].x*kk=a[t1].y; //a[t2].x*a[t2].x*k+a[t2].x*kk=a[t2].y; //double g=gcd(a[t1].x,a[t2].x); //double LCM=a[t1].x*a[t2].x/g; //(LCM/a[t1].x)*(a[t1].x*a[t1].x)*k=a[t1].y*LCM/a[t1].x; //(LCM/a[t2].x)*(a[t2].x*a[t2].x)*k=a[t2].y*LCM/a[t2].x; // (LCM/a[t1].x)*(a[t1].x*a[t1].x)-(LCM/a[t2].x)*(a[t2].x*a[t2].x)*k=a[t1].y*LCM/a[t1].x-a[t2].y*LCM/a[t2].x; tmp=(a[tm].y*a[tn].x-a[tn].y*a[tm].x)/(a[tn].x*a[tm].x*(a[tm].x-a[tn].x)); temp=(a[tn].y-a[tn].x*a[tn].x*tmp)/a[tn].x; if(tmp<0) return true; else return false; }*/ inline bool charge(int tmp,double k,double kk) { double temp=a[tmp].x*a[tmp].x*k+a[tmp].x*kk; if(fabs(temp-a[tmp].y)<eps) return true; else return false; } inline void dfs(int id,int cnt,int tot) { if(cnt+tot>=ans) return ; else if(id>n) { ans=cnt+tot; return ; } for(ri i=1; i<=cnt; ++i) { if(charge(id,par[i].a,par[i].b)) { dfs(id+1,cnt,tot); return ; } } for(ri i=1; i<=tot; ++i) { //cout<<single_pig[i].x<<" "<<single_pig[i].y<<endl; if(fabs(single_pig[i].x-a[id].x)<=eps) continue;//如果这两个猪x值相同，那肯凑不成一个抛物线，因为x>0,而抛物线一直过(0,0). tmp=(single_pig[i].y*a[id].x-a[id].y*single_pig[i].x)/(a[id].x*single_pig[i].x*(single_pig[i].x-a[id].x));//我是不会告诉你我求tmp的时候没有和以前的单猪求，和a[i].x,a[i].y求得解析式。 temp=(a[id].y-a[id].x*a[id].x*tmp)/a[id].x; if(tmp<0) { par[cnt+1].a=tmp; par[cnt+1].b=temp; double tx=single_pig[i].x; double ty=single_pig[i].y; for(ri j=i; j<tot; ++j) { single_pig[j].x=single_pig[j+1].x; single_pig[j].y=single_pig[j+1].y; } dfs(id+1,cnt+1,tot-1); for(ri j=tot; j>i; --j) { single_pig[j].x=single_pig[j-1].x; single_pig[j].y=single_pig[j-1].y; } single_pig[i].x=tx; single_pig[i].y=ty; } } single_pig[tot+1].x=a[id].x; single_pig[tot+1].y=a[id].y; dfs(id+1,cnt,tot+1); } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(a,0,sizeof a); for(ri i=1; i<=n; ++i) scanf("%lf%lf",&a[i].x,&a[i].y); ans=0x3f; dfs(1,0,0); printf("%d\n",ans); } return 0; } ```