最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定 $n$ 个 pig 的坐标，其中第 $i$ 个 pig 的坐标为 $(x_i,y_i)$

弹弓的坐标是 $(0,0)$，弹弓一次可以发射一条轨迹是抛物线的子弹，并且可以消灭该条抛物线上所有的 pig

求解一个方案，使得弹弓发射的所有子弹可以消灭所有的 pig 且弹弓 发射次数最少

本题的参数 $m$ 是要求大数据搜索优化的，也就是用 Dancing Links 做的 重复覆盖问题
但这不在本篇题解的讨论范围之内（以后有机会可以更）

分析

首先分析一下我们用弹弓发射的子弹的轨迹有哪些特点：$y=ax^2+bx+c$

1. 一条经过原点的抛物线 $c = 0$
2. 抛物线的开口朝下 $a<0$

这样抛物线方程就可以设为：$y=ax^2+bx$

方程中有两个参数 $a$ 和 $b$，因此我们可以用具体两个点的坐标来唯一的确定一条 抛物线

参数的计算公式如下：

$$ {\begin{cases} y_1 = ax_1^2 + bx_1 \\\ y_2 = ax_2^2 + bx_2\end{cases}} \quad \Rightarrow \quad {\begin{cases} a = \dfrac{\dfrac{y_1}{x_1} - \dfrac{y_2}{x_2}}{x_1 - x_2}\\\ b = \dfrac{y_1}{x_1} - ax_1\end{cases}} $$

于是我们就可以预处理出最多 $n^2$ 条抛物线，然后用这些抛物线对 点集 进行覆盖即可

用已知两点预处理出来的抛物线一定要满足合法（即$a<0$）

然后对于两点构成的抛物线，我们还要处理出他穿过的其他的点

这样预处理的时间复杂度就是 $O(n^3)$

到此处位置，我们就把问题转化为， 重复覆盖问题 （大家可以用搜索优化 Dancing Links 处理该问题 ）

本题解采用 状态压缩DP 来完成

闫氏DP分析法

状态表示—集合$f_i$：当前点集覆盖状态为 $i$ 的方案（$i$是采用二进制压缩存储的点集覆盖状态）
状态表示—属性$f_i$：方案用的抛物线数量最少 $Min$
状态表示—计算$f_i$：

$$ f_{ne} = min(f_i) + 1 $$

其中 $ne$ 是状态 $i$ 枚举到新抛物线，并进行覆盖以后生成的新状态 $ne$

初始状态 ：$f_0$
目标状态 ：$f_{1\cdots 1}$

Code

时间复杂度：
1. 预处理 $O(n^3)$
2. 状压DP $O(n2^n)$

#include <iostream>
#include <cstring>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 20, M = 1 << N;
const double eps = 1e-8;

int n, m;
PDD ver[N];
int path[N][N];
int f[M];

int cmp_lf(double a, double b)  //浮点数比较
{
    if (fabs(a - b) < eps) return 0;
    if (a > b) return 1;
    return -1;
}
void init_path()    //预处理所有的抛物线
{
    memset(path, 0, sizeof path);
    for (int i = 0; i < n; ++ i)
    {
        path[i][i] = 1 << i;    //单独生成一条只经过(0,0)和(x,y)的抛物线
        for (int j = 0; j < n; ++ j)
        {
            double x1 = ver[i].x, y1 = ver[i].y;
            double x2 = ver[j].x, y2 = ver[j].y;
            if (!cmp_lf(x1, x2)) continue;  //单独一个点无法生成参数a,b的抛物线
            double a = (y1 / x1 - y2 / x2) / (x1 - x2);
            double b = (y1 / x1) - a * x1;
            if (cmp_lf(a, 0.0) >= 0) continue;  //a < 0
            //参数a,b的抛物线已生成，枚举他经过的所有点
            for (int k = 0; k < n; ++ k)
            {
                double x = ver[k].x, y = ver[k].y;
                if (!cmp_lf(y, a * x * x + b * x)) path[i][j] += 1 << k;
            }
        }
    }
}
void solve()
{
    //input
    cin >> n >> m;
    for (int i = 0; i < n; ++ i) cin >> ver[i].x >> ver[i].y;
    //prework
    init_path();
    //dp
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int cur_st = 0; cur_st + 1 < 1 << n; ++ cur_st)
    {
        int t = -1;
        for (int i = 0; i < n; ++ i)
            if (!(cur_st >> i & 1))
                t = i;
        for (int i = 0; i < n; ++ i)
        {
            int ne_st = path[t][i] | cur_st;
            f[ne_st] = min(f[ne_st], f[cur_st] + 1);
        }
    }
    cout << f[(1 << n) - 1] << endl;
}
int main()
{
    int T = 1; cin >> T;
    while (T -- ) solve();
    return 0;
}