[NOIP2016]愤怒的小鸟 DP

题解：

　　首先观察数据范围，n <= 18,很明显是状压DP。所以设f[i]表示状态为i时的最小代价。然后考虑转移。

　　注意到出发点(0, 0)已经被固定，因此只需要2点就可以确定一条抛物线，所以每次转移时枚举是哪两只猪确定了这条抛物线，然后由于一条抛物线可能会恰好打中别的猪，所以再枚举判断一下哪些猪会被打中，然后就获得了一个后续状态，直接转移即可。

　　但是这样是$2^nn^3T$的复杂度，显然过不去，因此考虑优化。

　　1，因为一旦确定抛物线的2只猪确定了，这条抛物线会经过哪些其他的猪也就确定了，所以我们可以预处理出g[i][j],表示用第i和第j只猪确定抛物线时总共可以打到哪些猪。

　　2，因为观察到对于2条抛物线，先发射哪条不影响答案，同理，因为所有猪都必须被打，所以那只猪先被打掉也不影响答案，所以每次转移时只打状态中第一个没被打的猪，然后就可以break进入下一个状态了。因为这次没打的猪，下次还是会打掉的，因此不影响正确性。

　　于是复杂度$2^nnT$

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define eps 1e-9

 #define AC 20

 #define ac 300000

 #define ld long double

 int T, n, m, maxn;

 int f[ac], g[AC][AC];

 struct node{

     ld x, y;

 }pig[AC], func;

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 node cal(node x, node y)//计算解析式

 {

     ld a, b;

     a = (x.y * y.x - y.y * x.x) / (x.x * x.x * y.x - y.x * y.x * x.x);

     b = x.y / x.x - a * x.x;

     return (node){a, b};

 }

 inline void upmin(int &a, int b)

 {

     if(b < a) a = b;

 }

 bool check(node ff, node x)//计算一个点是否过解析式

 {

     ld a = ff.x, b = ff.y;

     return (fabs(x.y - (a * x.x * x.x + b * x.x)) <= eps);

 }

 void pre()

 {

     int x = , tmp;

     n = read(), m = read();

     maxn = ( << n) - ;

     memset(g, , sizeof(g));

     memset(f, , sizeof(f));

     f[] = ;

     for(R i = ; i <= n; i ++)

         scanf("%Lf%Lf", &pig[i].x, &pig[i].y);

     for(R i = ; i <= n; i ++, x <<= )

     {

         int now = ;

         for(R j = ; j <= n; j ++, now <<= )

         {

             if(i == j) {g[i][j] = x; continue;}

             tmp = x | now; func = cal(pig[i], pig[j]);

             if(func.x >= ) {g[i][j] = ; continue;}//不合法

             int t = ;

             for(R k = ; k <= n; k ++, t <<= )

             {

                 if(k == i || k == j) continue;

                 if(!check(func, pig[k])) continue;

                 tmp |= t;

             }

             g[i][j] = tmp;

         }

     }

 }

 void get()

 {

     for(R i = ; i <= maxn; i ++)

     {

         int x = ;

         for(R j = ; j <= n; j ++, x <<= )

         {

             if(i & x) continue;

             for(R k = ; k <= n; k ++)

                 upmin(f[i | g[j][k]], f[i] + );

             break;

         }

     }

     printf("%d\n", f[maxn]);

 }

 void work()

 {

     T = read();

     while(T --)

         pre(), get();

 }

 int main()

 {

 //    freopen("in.in", "r", stdin);

     work();

 //    fclose(stdin);

     return ;

 }

巴特西

[NOIP2016]愤怒的小鸟 DP

最新文章

热门文章