牛客竞赛题目讲解_愤怒的小鸟(noip)

//  https://ac.nowcoder.com/acm/problem/16431

#include "stdafx.h"

//#include <bits/stdc++.h>

#include <algorithm> 

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#define db double

#define mindb 1e-6

using namespace std;

int t,n,m,fly[20][20],f[300000];

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

float arr[32][2]={

1.00, 5.00,

2.00, 8.00,

3.00 ,9.00,

4.00, 8.00,

5.00, 5.00

};

int main()

{ 

//scanf("%d",&t);

//while (t--)

{

n=5;

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

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

//scanf("%lf%lf",&x[i],&y[i]);

{

x[i]=arr[i-1][0];

y[i]=arr[i-1][1];

}

/*

T={1,2,3,4,5}

21=  10101  表示子集  {1，3，5}

  */

// fly[i][j]表示i,j 两个点确定的抛物线所能经过哪些点

memset(fly,0,sizeof(fly));

for (int i=1;i<n;++i) fly[i][i]|=1<<(i-1);// 只剩下一个点也需要一条曲线

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

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

{

if (fabs(x[i]-x[j])<mindb) continue;

a=(y[i]/x[i]-y[j]/x[j])/(x[i]-x[j]);

if (a>=0) continue;

b=y[i]/x[i]-x[i]*a;

for (int k=1;k<=n;++k)

if (fabs(y[k]/x[k]-(a*x[k]+b))<mindb) fly[i][j]|=1<<(k-1);//预处理fly[i][j]

}

memset(f,0X3f,sizeof(f));

f[0]=0;//初始化

// f[s]表示目前被消灭的猪的情况是s, 最少使用的鸟(曲线)的数量

for (int s=0;s<(1<<n)-1;++s)

{

//找到任意一个不在s 中的列x

            int x = 0;

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

            {

                //i点不在s 中的列x

                if((s >> (i-1) & 1) == 0)

                {

                    x = i;

                    break;

                }

            }

            //枚举所有点，计算覆盖x点的新集合s| fly[x][j]的最优解

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

            {

                f[s | fly[x][i]] = min(f[s | fly[x][i]], f[s] + 1);

            } 

}

printf("%d\n",f[(1<<n)-1]);

}

return 0;

}