p2831——愤怒的小鸟

这题不就是暴力枚举吗,dfs爆搜就行,记一下前面有几条抛物线了,有几个单着的猪,分三种情况,如果来了一个新猪,满足前面的其中一条抛物线,那么直接向下搜即可(这样最优);新猪和以前单着的猪凑成一条抛物线;此猪作为一个单猪存在。 (算抛物线的a,b时,推式子推到**)

// 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;
}

发表于 2018-08-27 20:17:22 in 未分类