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

愤怒的小鸟

题目链接

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

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

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

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

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

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

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

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 #define N 20
 6 #define eps 1e-6
 7 #define INF 0x3f3f3f3f
 8 #define fabs(x) ((x)>0?(x):-(x))
 9 #define reset(a) memset(a,0,sizeof(a))
10 #define check(p,q,i) fabs(p*p*a[i]+p*b[i]-q)<=eps
11 int T,n,m,ans,cnt1,cnt2,dealta;
12 double X[N],Y[N],a[N],b[N];
13 double x[N],y[N];
14 bool used[N];
15 void dfs(int t){
16     if(cnt1+cnt2-dealta>=ans) return;    //剪枝 
17     if(t==n+1){
18         ans=cnt1+cnt2-dealta;
19         return;
20     }
21     bool flag=0;
22     for(int i=1;i<=cnt1;i++)
23      if(check(X[t],Y[t],i)){ flag=1;break; }    //若以前建的抛物线能打到这头猪 
24     if(flag){ dfs(t+1); return; }    //直接搜下一个    
25     for(int i=1;i<=cnt2;i++)
26      if(!used[i]){
27         if(fabs(X[t]-x[i])<=eps) continue;
28         double A=(X[t]*y[i]-x[i]*Y[t])/(X[t]*x[i]*x[i]-X[t]*X[t]*x[i]);    //两猪确定一条抛物线 
29         double B=(Y[t]-A*X[t]*X[t])/X[t];
30         if(A>=0) continue;        //抛物线开口不能朝上 
31         used[i]=1; dealta++;    //used[i]置为1相当于第i个单着的猪删去，cnt2-dealta为单着的猪的总数 
32         a[++cnt1]=A; b[cnt1]=B;
33         dfs(t+1);
34         cnt1--;        //回溯 
35         used[i]=0; dealta--; 
36     }
37     x[++cnt2]=X[t]; y[cnt2]=Y[t];
38     dfs(t+1);
39     cnt2--;
40 }
41 int main(){
42     scanf("%d",&T);
43     while(T--){
44         reset(X); reset(Y);
45         ans=INF; cnt1=cnt2=dealta=0;
46         reset(x); reset(y); reset(used);
47         scanf("%d%d",&n,&m);
48         for(int i=1;i<=n;i++)
49          scanf("%lf%lf",&X[i],&Y[i]);    //读入坐标 
50         dfs(1); printf("%d
",ans);
51     }
52     return 0;
53 }