【洛谷P2831】[NOIP2016]愤怒的小鸟

愤怒的小鸟

题目链接

本来是刷状压DP的，然而不会。。

搜索是比较好想的，直接dfs就行了

我们可以知道两只猪确定一条抛物线

依次处理每一只猪，有以下几种方法：

1.先看已经建立的抛物线是否能打到这只猪

2.若1不可行，将这只猪与之前单着的猪配对，建抛物线

3.将这只猪单着，等待以后配对(若配不上，直接建一个只打一头猪的抛物线)

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define N 20

 #define eps 1e-6

 #define INF 0x3f3f3f3f

 #define fabs(x) ((x)>0?(x):-(x))

 #define reset(a) memset(a,0,sizeof(a))

 #define check(p,q,i) fabs(p*p*a[i]+p*b[i]-q)<=eps

 int T,n,m,ans,cnt1,cnt2,dealta;

 double X[N],Y[N],a[N],b[N];

 double x[N],y[N];

 bool used[N];

 void dfs(int t){

     if(cnt1+cnt2-dealta>=ans) return;    //剪枝

     if(t==n+){

         ans=cnt1+cnt2-dealta;

         return;

     }

     bool flag=;

     for(int i=;i<=cnt1;i++)

      if(check(X[t],Y[t],i)){ flag=;break; }    //若以前建的抛物线能打到这头猪

     if(flag){ dfs(t+); return; }    //直接搜下一个

     for(int i=;i<=cnt2;i++)

      if(!used[i]){

         if(fabs(X[t]-x[i])<=eps) continue;

         double A=(X[t]*y[i]-x[i]*Y[t])/(X[t]*x[i]*x[i]-X[t]*X[t]*x[i]);    //两猪确定一条抛物线

         double B=(Y[t]-A*X[t]*X[t])/X[t];

         if(A>=) continue;        //抛物线开口不能朝上

         used[i]=; dealta++;    //used[i]置为1相当于第i个单着的猪删去，cnt2-dealta为单着的猪的总数

         a[++cnt1]=A; b[cnt1]=B;

         dfs(t+);

         cnt1--;        //回溯

         used[i]=; dealta--;

     }

     x[++cnt2]=X[t]; y[cnt2]=Y[t];

     dfs(t+);

     cnt2--;

 }

 int main(){

     scanf("%d",&T);

     while(T--){

         reset(X); reset(Y);

         ans=INF; cnt1=cnt2=dealta=;

         reset(x); reset(y); reset(used);

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

         for(int i=;i<=n;i++)

          scanf("%lf%lf",&X[i],&Y[i]);    //读入坐标

         dfs(); printf("%d\n",ans);

     }

     return ;

 }