python/TangDou/AcWing/StateCompression/524.md

##AcWing 524. 愤怒的小鸟

一、题目描述

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

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

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

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

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

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

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

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

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

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

这些指令将在输入格式中详述。 

假设这款游戏一共有 T 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。  

由于她不会算，所以希望由你告诉她。

注意:本题除 NOIP 原数据外，还包含加强数据。

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

下面依次输入这 T 个关卡的信息。

每个关卡第一行包含两个非负整数 n,m，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。

接下来的 n 行中，第 i 行包含两个正实数 (x_i,y_i)，表示第 i 只小猪坐标为 (x_i,y_i)，数据保证同一个关卡中不存在两只坐标完全相同的小猪。

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

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

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

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

上文中，符号 ⌈c⌉ 和 ⌊c⌋ 分别表示对 c 向上取整和向下取整，例如 ：⌈2.1⌉=⌈2.9⌉=⌈3.0⌉=⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。

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

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

数据范围

输入样例：

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

输出样例：

1
1

二、题目解析

先从理解抛物线切入逐渐理解整个题目

抛物线 y=ax^2+bx+c

题意给出小鸟一定从 (0,0) 点飞出 , 可以得出限制抛物线的条件: a<0,c=0

注：a<0表示一定要开口向下

任意两点可以唯一确定一条抛物线:

抛物线有两种情况

• 一只小鸟只打一只小猪

当x_1=x_2

• 一只小鸟最少打两只小猪（也可以是3,4,5,...只）

为啥这么划分呢？因为题目中说了，要想一次打两只以上，那就是一条抛物线，而且，这条抛物线过原点，只要知道两个点(x_1,y_1),(x_2,y_2)就可以确定唯一的抛物线。

但是如果一次只打一只小猪的情况，就是在抛物线上只有一个固定点，那么a,b是无法唯一确定的。为什么会有这种情况发生呢？比如(x_1,y_1),(x_2,y_2)这两个点，横坐标是相同的(x_1=x_2)，按上面的推导式来看，就是分母是x_1-x_2=0，此时a,b是无法求解的，代表不存在这样的抛物线。

为啥没有抛物线呢？因为它们的横坐标相同,也就是那构成不了抛物线！但这样的情况确实是存在的，也是合法的。

数组含义 path[i][j]表示编号为i的猪和编号为j的猪，构成的抛物线能够打中所有猪的二进制表示式(转化为一个二进制存储)

例如: path[1][6] = 100101_b 表示由1号猪和6号猪确定的抛物线可以消灭编号1，3，6的小猪。

两只小猪确定下来的抛物线，并不是只能击中两个小猪，可能还有其它的小猪也在此路线上： 枚举所有的猪，判断其是否在此抛物线上，如果在就更新path[i][j]所表示的状态

状态表示 f[i]表示所有能够击败i表示的命中i_{count}只小猪时的方案中，使用的最少小鸟数

例 f[101001_b]:代表可以命中1,3,6三只小猪时，使用的最少抛物线数量,也就是小鸟的数量。

状态计算 找到i状态下没有被消灭的小猪的编号x，枚举可消灭它的抛物线path[x][j]

\large f[i|path[x][j]]=min(f[i|path[x][j],f[i]+1)

状态更新 state：表示一个状态 new_state：表示一个由state状态转化成的新的状态 则有 new_state=state|path[i][j]

注意边界

• 当只有一个猪时其状态是p[i][i]=1<<i;

• 题目中计算过程的变量类型都设置为double型 ，防止丢失精度(读入的时候就是double)

• 状态的初始化开始时除了f[0],其他所有状态都为无穷大，保证计算是不会被用到 f[0]表示的是，状态为0的二进制时，所需要打掉所有猪的最少抛物线数量

• 最后枚举所有状态，进行状态计算时，只需要更新到(1<<n)-2即可 因为(1<<n)-1的二进制全为1，此时所有的猪都已经被打掉，已经不用去添加抛物线了 所有不需要枚举此状态进行更新

Q: 为什么状态转移中只需要寻找第一个未被打掉的小猪，而不是枚举每一个未被打掉的小猪进行转移？

答：每一个小猪都必须被打掉，打掉小猪的先后顺序并不重要，因此我们不妨假设最小的抛物线中，我们将抛物线按照这样的顺序排序：即优先将当前状态中最小的没被覆盖的小鸟先打掉，这并不影响最终结果嘛。对于每一只小猪，枚举每一种可以将其覆盖掉的抛物线，得到一个新的状态，更新那个状态即可。那么如果一个状态序列是最优解，则这个状态的数据必定是正确的。

你想一想，先打 1,4，再打 2,3，和先打 2,3，再打 1,4 是不是一样的？

抽象成动态规划的打 DP表的思考方式，就是上一行数据，是从左向右依次填充，而是跳着填充，只要不影响本行填充，就是好的填充。

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 18;           // 小猪的数量上限
const int M = 1 << N;       // 用二进制可以模拟出N只小猪的所有状态 0~2^N-1种状态
const double eps = 1e-8;    // 浮点数的精度
const int INF = 0x3f3f3f3f; // 正无穷

// 结构体，小猪坐标
struct Node {
    double x, y;
} pig[N];

int path[N][N]; // path[i][j]:第i只和第j只小猪构成的抛物线能覆盖的所有状态(是一个状态压缩值，比如0101=5)
int f[M];       // f[i]表示覆盖掉目前i的状态表示中所有小猪，最少需要多少条抛物线，也就是最少需要多少只小鸟
int n;          // n只小猪
int m;          // Kiana 输入的神秘指令类型，此变量没有用到,据说可以用来骗分，没有仔细研究

int cmp(double a, double b) { // 浮点数比较
    return abs(a - b) < eps;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d%d", &n, &m);
        // 读入每只小猪的坐标位置
        for (int i = 0; i < n; i++) scanf("%lf%lf", &pig[i].x, &pig[i].y); // 因为采用状压DP，下标从0开始

        // 1、预处理所有可能的抛物线，记录抛物线与每个小猪的覆盖关系
        memset(path, 0, sizeof path); // 多组数据，每次清空

        /*通过分析知道 y=ax^2+bx (∵小鸟从圆点出发，∴c=0)
          如何确定一条抛物线呢？其实就是确定下来a,b的值。
          方法是通过枚举任意两个小猪：(x1,y1),(x2,y2)确定下来一条抛物线
        */
        for (int i = 0; i < n; i++) {         // 枚举第一只小猪
            path[i][i] = 1 << i;              // 注意:存在某些只覆盖一个点的抛物线,这个不容易想到，但打过愤怒的小鸟游戏的人，应该都知道一次未必就能打下两只以上的小猪
            for (int j = i + 1; j < n; j++) { // j从i+1开始，防止出现重复，比如(1,3)和(3,1)其实是同一条抛物线
                double x1 = pig[i].x, y1 = pig[i].y;
                double x2 = pig[j].x, y2 = pig[j].y;
                if (cmp(x1, x2) & cmp(y1, y2)) continue; // 如果存在重复输入的数据, 事实上出题人比较良心，没有给我们准备恶心的特判数据
                // 但是，为了保护下面的代码运算过程中肯定不出错，做为一个程序员，还是要加上上面这句cmp
                double a = (y1 / x1 - y2 / x2) / (x1 - x2); // 推式子,见题解
                double b = (y1 / x1) - a * x1;              // 推式子,见题解
                if (a >= 0) continue;                       // 抛物线开口需要向下

                // 此抛物线可以覆盖掉哪些小猪
                for (int k = 0; k < n; k++) {
                    double x = pig[k].x, y = pig[k].y;
                    if (cmp(a * x * x + b * x, y)) // 符合抛物线方程，代表此抛物线可以覆盖掉k点
                        path[i][j] += 1 << k;      // 记录此抛物线方程覆盖掉k号小猪
                }
            }
        }
        /*
         2、DP 解决用最少多少条抛物线才能完全覆盖掉所有小猪
         起点：0000 终点:1111
         办法：对于没有覆盖的小猪，引入经过它的抛物线，对比记录最小代价解
         原来就是1的，不用管了，只考虑状态是0的就对了。
         */
        memset(f, 0x3f, sizeof f); // 预求最小，先设最大,表示状态不合法或没有计算过
        f[0] = 0;                  // 递推起点，一只小猪也不覆盖掉，需要0条抛物线，这在现实中是合理的解释。

        for (int x = 0; x < (1 << n) - 1; x++) { // 枚举每个存在0的状态,　(1<<n)-1类似于 111111这样的形式，因为现在的目标是找出含有数位是0的状态进行状态转移，所以全是1的不用考虑
            if (f[x] == INF) continue;           // 如果当前状态是一个未推导状态，那么也不指望它能帮助其它人提供信息

            for (int i = 0; i < n; i++) {         // 枚举状态x的每一个数位，也可以理解为每一只小猪，看看它是不是还没有被覆盖到
                if ((x >> i & 1) == 0) {          // i号小猪现在还没有被覆盖到
                    for (int j = 0; j < n; j++) { // 枚举i号小猪参与的所有抛物线
                        if (path[i][j]) {
                            int k = path[i][j] | x;     // 引入此抛物线(i,j)，可以在x状态基础上覆盖掉更多的小猪，到达k状态
                            f[k] = min(f[k], f[x] + 1); // 记录k状态是通过x状态在增加一条抛物线的代价下到达的
                        }
                    }
                    break;
                   
                }
            }
        }
        // 递推的结果保存在所有状态都是1的结果数组中
        printf("%d\n", f[(1 << n) - 1]);
    }
    return 0;
}