NOIP 2016 D2T3 愤怒的小鸟

胡雨菲菲

题目描述

Kiana最近沉迷于一款神奇的游戏无法自拔。

简单来说，这款游戏是在一个平面上进行的。

有一架弹弓位于（0,0)处，每次Kiana可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如y=ax^2+bx的曲线，其中a,b是Kiana指定的参数，且必须满足a<0。

当小鸟落回地面（即x轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有n只绿色的小猪，其中第i只小猪所在的坐标为(xi,yi)。

如果某只小鸟的飞行轨迹经过了(xi,yi),那么第i只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；

如果一只小鸟的飞行轨迹没有经过(xi,yi)，那么这只小鸟飞行的全过程就不会对第i只小猪产生任何影响。

例如，若两只小猪分别位于（1,3)和（3,3)，Kiana可以选择发射一只飞行轨迹为y=-x^2+4x的小鸟，这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有T个关卡，现在Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。

输入输出格式 输入格式：

第一行包含一个正整数T，表示游戏的关卡总数。

下面依次输入这T个关卡的信息。每个关卡第一行包含两个非负整数n,m，分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。接下来的n行中，第i行包含两个正实数(xi,yi)，表示第i只小猪坐标为(xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果m=0，表示Kiana输入了一个没有任何作用的指令。

如果m=1，则这个关卡将会满足：至多用只小鸟即可消灭所有小猪。

如果m=2,则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少只小猪。

保证1<=n<=18，0< =m<=2，0< xi,yi<10，输入中的实数均保留到小数点后两位。

上文中，符号和分别表示对c向上取整和向下取整

输出格式：

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量

胡雨菲菲

先预处理出每条抛物线能打到的鸟，然后状压DP

1. #include <cstdio>
   
2. #include <cmath>
   
3. #include <algorithm>
   
4. #include <cstring>
   
5. #include <iostream>
   
6. const double eps = 1e-9;
   
7. const int N = 20;
   
8. 
   
9. int n, f[1 << N], p[N][N];
   
10. double x[N], y[N];
    
11. 
    
12. inline bool equal(const double &a, const double &b) {
    
13.     return fabs(a - b) <= eps;
    
14. }
    
15. 
    
16. void init() {
    
17.     for(int i = 0; i < n; i++) {
    
18.         f[1 << i] = 1;
    
19.     }
    
20.     for(int i = 0; i < n; i++) {
    
21.         for(int j = 0; j < i; j++) {
    
22.             if(x[i] == x[j]) continue;
    
23.             double t1 = y[i] * x[j];
    
24.             double t2 = y[j] * x[i];
    
25.             double t = x[i] * x[j] * (x[i] - x[j]);
    
26.             double a = (t1 - t2) / t;
    
27.             double b = (x[j] * t1 - x[i] * t2) / (t * -1);
    
28.             if(a >= 0) continue; /// a < 0
    
29.             if(equal(a, 0.0)) continue;/// a == 0
    
30.             f[(1 << i) | (1 << j)] = 1;
    
31.             for(int k = 0; k < n; k++) {
    
32.                 if(equal(a * x[k] * x[k] + b * x[k], y[k])) {
    
33.                     p[i][j] |= (1 << k);
    
34.                 }
    
35.             }
    
36.             p[j][i] = p[i][j];
    
37.             f[p[i][j]] = 1;
    
38.         }
    
39.     }
    
40.     return;
    
41. }
    
42. 
    
43. void cal(int a) {
    
44.     int t[N], u = 0;
    
45.     memset(t, 0, sizeof(t));
    
46.     while(a) {
    
47.         t[++u] = a & 1;
    
48.         a = a >> 1;
    
49.     }
    
50.     for(int i = n + 1; i >= 1; i--) {
    
51.         printf("%d", t[i]);
    
52.     }
    
53.     return;
    
54. }
    
55. 
    
56. int search(int sta) {
    
57.     //printf("search\n");
    
58.     //cal(sta);
    
59.     //printf("\n");
    
60.     if(f[sta]) {
    
61.         return f[sta];
    
62.     }
    
63.     int ans = n;
    
64.     for(int i = 0; i < n; i++) {
    
65.         for(int j = 0; j < i; j++) { /// 枚举抛物线
    
66.             if(((sta >> i) & 1) && ((sta >> j) & 1) && p[i][j]) { ///抛物线要存在
    
67.                 ans = std::min(ans, search(sta & (~p[i][j])) + 1);
    
68.             }
    
69.         }
    
70.     }
    
71.     for(int i = 0; i < n; i++) {
    
72.         if((sta >> i) & 1) {
    
73.             ans = std::min(ans, search(sta & (~(1 << i))) + 1);
    
74.         }
    
75.     }
    
76.     f[sta] = ans;
    
77.     return ans;
    
78. }
    
79. 
    
80. void clear() {
    
81.     memset(f, 0, sizeof(f));
    
82.     memset(p, 0, sizeof(p));
    
83.     return;
    
84. }
    
85. 
    
86. int main() {
    
87.     int m, T;
    
88.     scanf("%d", &T);
    
89.     while(T--) {
    
90.         clear();
    
91.         scanf("%d%d", &n, &m);
    
92.         //printf("%d %d \n", n, m);
    
93.         for(int i = 0; i < n; i++) {
    
94.             //printf("%d\n", i);
    
95.             std::cin >> x[i] >> y[i];
    
96.         }
    
97. 
    
98.         init();
    
99. 
    
100.         printf("%d\n", search((1 << n) - 1));
     
101.     }
     
102.     return 0;
     
103. }
     

复制代码