【NOIP2016】愤怒的小鸟

CJOJ——P2257 【NOIP2016】愤怒的小鸟

题意

??给定$n$只猪的坐标，每一只小鸟能走出一条抛物线的轨迹，至少需要多少只鸟才能把这些猪全部打掉

解法

状压$DP$：
??先对题目输入的坐标进行处理：
??枚举两只猪，求出抛物线，然后计算有多少只猪在这条抛物线上，利用状态压缩进行储存
??注意，对于单独的，不在任意一条上述抛物线上的猪要额外加一条抛物线
??对于从$0$到$2^n-2$开始的每一个状态$now$，都枚举所有的抛物线状态$P_i$，令$u=now|P_i$，则$u$为目标状态
令$f_u$表示要实现$u$需要多少条抛物线
则$f_u=min（f_u，f_{now}+1）$，$f_{2^n-1}$就是答案

复杂度

O（$n^2+2^n*cnt$），$cnt$为抛物线条数

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
bool vis[20];
double x[20];
double y[20];
int f[(1<<20)];//状压进行记忆化搜索,0表示不在当前状态的抛物线上，1则反之
int p[20*20];//表示用一只小鸟在打中编号为i和j的小猪的前提下所能打中的小猪序列，如001010100......
int T,n,m,ans,cnt;
int main( )
{double X,Y,a,b;scanf("%d",&T);while( T-- ){scanf("%d%d",&n,&m);for(int i=0;i<=n-1;i++){scanf("%lf%lf",&X,&Y);x[ i ]=X;y[ i ]=Y;}memset( f,100,sizeof f );memset( vis,0,sizeof vis );memset( p,0,sizeof p );f[ 0 ]=0;cnt=0;for(int i=0;i<=n-1;i++)//枚举两个点，进行计算，求出抛物线for(int j=i+1;j<=n-1;j++){if( x[ i ]==x[ j ] )continue ;/*解方程y=a*x*x+b*x:易知:a=( y-b*x )/( x*x )a*x[ i ]*x[ i ]+b*x[ i ]=y[ i ]  -----①a*x[ j ]*x[ j ]+b*x[ j ]=y[ j ]  -----②①*x[ j ]*x[ j ]②*x[ i ]*x[ i ]①-②:b*x[ i ]*x[ j ]*x[ j ]-b*x[ j ]*x[ i ]*x[ i ]=y[ i ]*x[ j ]*x[ j ]-y[ j ]*x[ i ]*x[ i ]合并同类项:b*x[ i ]*x[ j ]*(x[ j ]-x[ i ])=y[ i ]*x[ j ]*x[ j ]-y[ j ]*x[ i ]*x[ i ]系数化为1:b=( y[ i ]*x[ j ]*x[ j ]-y[ j ]*x[ i ]*x[ i ] )/( x[ i ]*x[ j ]*(x[ j ]-x[ i ]) )*///a=( y[ i ]*x[ j ]-y[ j ]*x[ i ] )/( x[ i ]*x[ i ]*x[ j ]-x[ j ]*x[ j ]*x[ i ] );b=( y[ i ]*x[ j ]*x[ j ]-y[ j ]*x[ i ]*x[ i ] )/( x[ i ]*x[ j ]*(x[ j ]-x[ i ]) );a=(y[ j ]-b*x[ j ])/(x[ j ]*x[ j ]);if( a>=-(1e-6) )//题目要求a<0continue;cnt++;vis[ i ]=vis[ j ]=1;for(int k=0;k<=n-1;k++)//看还有多少只猪在这个抛物线上if( abs( ( a*x[ k ]*x[ k ]+b*x[ k ] )-y[ k ] )<(1e-8) )//判断第k只猪是否在抛物线上{vis[ k ]=1;p[ cnt ]|=(1<<k);}}//处理只能过一点的抛物线for(int i=0;i<=n-1; i++)if( !vis[ i ] ) p[ ++cnt ]|=(1<<i);//枚举状态与抛物线 int u;for(int now=0;now<=(1<<n)-2;now++)for(int i=1;i<=cnt;i++){u=now|p[ i ];if( f[ u ]>f[ now ]+1 )f[ u ]=f[ now ]+1;}printf("%d\n",f[ (1<<n)-1 ] );}return 0;
}