[NOIP 2016] 愤怒的小鸟

[题目链接]

           http://uoj.ac/problem/265

[算法]

         首先 ， 可以通过枚举两点计算出抛物线

         用Fi表示打掉集合i所需的最少抛物线 ， 每次转移只需枚举第一个没打到的点即可

         时间复杂度 : O(2 ^ n * n ^ 2)

[代码]

         

#include<bits/stdc++.h>
using namespace std;
#define MAXN 20
const int MAXS = 1 << 20;
const double EPS = 1e-10;

int n , m;
int value[MAXN][MAXN];
int dp[MAXS];
double x[MAXN],y[MAXN];

inline void init()
{
    memset(value,0,sizeof(value));
    memset(dp,0x3f,sizeof(dp));    
}

int main()
{
    
    int T;
    scanf("%d",&T);
    while (T--)
    {
        init();
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= n; i++) scanf("%lf%lf",&x[i],&y[i]);
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                 if (fabs(x[i] - x[j]) < EPS) continue;
                 double 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[j] * x[j] * x[i] - x[j] * x[i] * x[i]);
                 if (a > 0 || (a > -EPS && a < EPS)) continue;
                 for (int k = 1; k <= n; k++)
                 {
                      if (fabs(y[k] - a * x[k] * x[k] - b * x[k]) < EPS) 
                            value[i][j] |= 1 << (k - 1);             
                 }     
            }    
        }    
        dp[0] = 0;
        for (int i = 0; i < (1 << n);  i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if ((i & (1 << (j - 1))) == 0)
                {
                    for (int k = j + 1; k <= n; k++)
                         dp[i | value[j][k]] = min(dp[i | value[j][k]],dp[i] + 1);
                    dp[i | (1 << (j - 1))] = min(dp[i | (1 << (j - 1))],dp[i] + 1);
                    break;
                }
            }
        }
        printf("%d
",dp[(1 << n) - 1]);
    }
        
    return 0;
}