NOIP愤怒的小鸟

愤怒的小鸟

Description:

给你\(n<=18\)个小猪，发射的小鸟轨迹为抛物线，求最小用多少个小鸟可以将小猪全部干掉

看到n很小，我想到了搜索，于是我用\(dfs\)枚举出，每个抛物线打掉的小猪集合然后判断他的合法性,结果TLE成了50分，mmp，瞄了一眼题解，看到他是枚举小猪，来确定抛物线，感觉妙了很多，于是我写了如下的

code:

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const double eps=0.0000001;

int t,n,m,ans;

double x[20],y[20],a[20],b[20];

bool vis[20];

inline double fabs(double x){

    if(x<0)return -x;

    else return x;

}

inline void dfs(int pos,int num,int cnt){

//当前决策第几个位置，构造了多少个抛物线，剩下几个独立的

    if(pos>n){

        ans=min(ans,num+cnt);

        return ;

    }

    bool flag=0;

    for(int i=1;i<=num;++i){//枚举是否可以被前面的抛物线覆盖

        double xx=a[i]*x[pos]*x[pos]+b[i]*x[pos];

        double yy=y[pos];

        if(fabs(fabs(xx)-fabs(yy))<=eps&&(xx*yy>0)){

        flag=1;

        vis[pos]=1;//不独立

        dfs(pos+1,num,cnt-1);

        vis[pos]=0;

        break;

       }

    }

    if(flag)return ;

    for(int i=1;i<pos;++i){

      if(vis[i])continue;//不独立

      double a1=x[i];

      double b1=y[i];

      double a2=x[pos];

      double b2=y[pos];

      double aa=(b1*a2-b2*a1)/(a1*a1*a2-a1*a2*a2);

        double bb=(a1*a1*b2-a2*a2*b1)/(a1*a1*a2-a2*a2*a1);

        if(aa>=0)continue;//不可行

        a[num+1]=aa;

        b[num+1]=bb;//可行

        vis[i]=vis[pos]=1;//不独立了

        dfs(pos+1,num+1,cnt-2);

        a[num+1]=0;

        b[num+1]=0;

        vis[i]=vis[pos]=0;//回溯

    }

    dfs(pos+1,num,cnt);//自己独立

}

int main(){

   scanf("%d",&t);

   for(int i=1;i<=t;++i){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;++i)scanf("%lf%lf",&x[i],&y[i]);

    ans=0x3f3f3f3f;

    dfs(1,0,n);

    cout<<ans<<endl;

   }

}

80分还是TLE

于是乎，又瞄了一眼题解,他加了一个最优性剪枝\(num+cnt>=ans,return ;\)

于是我也加了一个，这下可惨了，一下WA成了40

注意看我的代码，\(dfs(pos+1,num,cnt-1)\text{&&}dfs(pos+1,num+1,cnt-2)\text{&&}dfs(pos+1,num,cnt)\)

\(num+cnt\)的总和是变小了，如果使用最优性剪枝，有可能将最优值剪掉

仔细比较题解和我的代码,他并不是把所有的小猪刚开始都变成独立的，这样对于一个新小猪,他的code

\(dfs(pos+1,num,cnt)\text{&&} dfs(pos+1,num+1,cnt-1)\text{&&}dfs(pos+1,num,cnt+1)\)

\(num+cnt\)的总和单调不降,可以使用最优性剪枝

我是上来就把所有小猪看成独立，而他是将小猪后放进去

code:

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

using namespace std;

const double eps=1e-8;

int t,n,m,ans;

double x[20],y[20],a[20],b[20],xx[20],yy[20];

inline void dfs(int pos,int num,int cnt){

    if(num+cnt>=ans)return ;//最优性剪枝

    if(pos>n){

        ans=num+cnt;

        return ;

    }//边界

    bool flag=0;

    for(int i=1;i<=num;++i){//枚举是否可以被前面的抛物线覆盖

        double xx=a[i]*x[pos]*x[pos]+b[i]*x[pos];

        double yy=y[pos];

        if(fabs(xx-yy)<eps){

      	dfs(pos+1,num,cnt);

        flag=1;

      	break;

       }

    }

  if(!flag){

    for(int i=1;i<=cnt;++i){

    	double a1=xx[i];

    	double b1=yy[i];

    	double a2=x[pos];

    	double b2=y[pos];

      if(fabs(a1-a2)<=eps)continue;

    	double aa=(b1*a2-b2*a1)/(a1*a1*a2-a1*a2*a2);

      double bb=(a1*a1*b2-a2*a2*b1)/(a1*a1*a2-a2*a2*a1);

        if(aa>=0)continue;//不可行

        a[num+1]=aa;

        b[num+1]=bb;

        double va=xx[i];

        double vb=yy[i];

        for(int j=i;j<cnt;++j){

          xx[j]=xx[j+1];

          yy[j]=yy[j+1];

        }

        dfs(pos+1,num+1,cnt-1);

        for(int j=cnt;j>i;j--)

                {

                    xx[j]=xx[j-1];

                    yy[j]=yy[j-1];

                }

                xx[i]=va;

                yy[i]=vb;

    }

    xx[cnt+1]=x[pos];

    yy[cnt+1]=y[pos];

    dfs(pos+1,num,cnt+1);//自己独立

  }

}

int main(){

   scanf("%d",&t);

   for(int i=1;i<=t;++i){

   	scanf("%d%d",&n,&m);

   	for(int i=1;i<=n;++i)scanf("%lf%lf",&x[i],&y[i]);

   	ans=0x3f3f3f3f;

   	dfs(1,0,0);

   	cout<<ans<<endl;

   }

}

搜索：状态要定好，剪枝要想好

巴特西

NOIP愤怒的小鸟

愤怒的小鸟

Description:

给你\(n<=18\)个小猪，发射的小鸟轨迹为抛物线，求最小用多少个小鸟可以将小猪全部干掉

看到n很小，我想到了搜索，于是我用\(dfs\)枚举出，每个抛物线打掉的小猪集合然后判断他的合法性,结果TLE成了50分，mmp，瞄了一眼题解，看到他是枚举小猪，来确定抛物线，感觉妙了很多，于是我写了如下的

code:

80分还是TLE

于是乎，又瞄了一眼题解,他加了一个最优性剪枝\(num+cnt>=ans,return ;\)

于是我也加了一个，这下可惨了，一下WA成了40

注意看我的代码，\(dfs(pos+1,num,cnt-1)\text{&&}dfs(pos+1,num+1,cnt-2)\text{&&}dfs(pos+1,num,cnt)\)

\(num+cnt\)的总和是变小了，如果使用最优性剪枝，有可能将最优值剪掉

仔细比较题解和我的代码,他并不是把所有的小猪刚开始都变成独立的，这样对于一个新小猪,他的code

\(num+cnt\)的总和单调不降,可以使用最优性剪枝

我是上来就把所有小猪看成独立，而他是将小猪后放进去

code:

搜索：状态要定好，剪枝要想好

最新文章

热门文章