noip 2016(愤怒的小鸟)（状压dp）

状压dp，每位代表一只猪，1为猪打到了，0为猪还没打到

两个猪的坐标确定一条抛弧线（即为打出鸟的轨迹）

g[i][j]表示由i猪和j猪确定的抛弧线，能打到的猪。（是一个二进制的状态）

预处理：把能被i猪和j猪确定的这条抛弧线能打到的猪都用状压的1来表示，存到g[i][j]里。

dp[s]表是当状态为s时所需要的最少抛弧线（最少小鸟）；

当发射轨迹为i猪和j猪确定的抛弧线的小鸟时 dp[s|g[i][j]]>dp[s]+1， dp[s|g[i][j]]=dp[s]+1；

求需要最少的抛物线数量（最少小鸟），把dp赋初值为很大的数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int g[20][20],dp[1<<20],n,m;
double x23[20],y23[20];
void yuchuli(int zhu1,int zhu2,double x1f,double x1,double y1,double x2f,double x2,double y2)
{
 double x=x1f/x1*x2;
 double xx=x1/x1*x2;
 double y=y1/x1*x2;
 double a=(y-y2)/(x-x2f);
 x=x1f/x1f*x2f;
 xx=x1/x1f*x2f;
 y=y1/x1f*x2f;
 double b=(y-y2)/(xx-x2);
 if(a>=0) return ;//a>=0没有任何猪能打掉，不合法
 for(int i=1;i<=n;i++)
 if(abs(a*x23[i]*x23[i]+b*x23[i]-y23[i])<=1e-6)//abs是必要的负数可以负很多
 g[zhu1][zhu2]|=(1<<(i-1)) ;
}
int main()
{
 //freopen("angrybirds.in","r",stdin);
// freopen("angrybirds.out","w",stdout);
 int t;
 cin>>t;
 for(int z=1;z<=t;z++)
 {
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
  scanf("%lf%lf",&x23[i],&y23[i]);
     memset(dp,127,sizeof(dp));
     memset(g,0,sizeof(g));
     for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
 {
 if(i!=j)yuchuli(i,j,x23[i]*x23[i],x23[i],y23[i],x23[j]*x23[j],x23[j],y23[j]); //抛物线，两个点确定一条抛物线
 }
     for(int i=1;i<=n;i++)
       g[i][i]=(1<<(i-1));
      dp[0]=0;
      for(int s=0;s<=(1<<n)-1;s++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
  if(dp[s|g[i][j]]>1+dp[s])
       dp[s|g[i][j]]=1+dp[s];
     printf("%d\n",dp[(1<<n)-1]);
    } 
 return 0;    
}