【洛谷题解/NOIP2016提高组】P2831 愤怒的小鸟

原题链接：https://www.luogu.com.cn/problem/P2831
难度：提高+/省选-（TG D2T3）
涉及知识点：数学【抛物线（二次函数）】、状态压缩DP

题意

在一个平面直角坐标系上，点 $(0,0)$ 处是一架弹弓，给定 $n$ 个形如 $(x,y)$ 的坐标，表示小猪的分布点，要求求出至少需要打出多少只小鸟才能把所有小猪消灭，小鸟的飞行轨迹是形 $y=a{x}^2+bx(a<0)$ 的曲线（向下开口的抛物线）。以及给出了一些对正解没有实质帮助但有助于暴力求解时优化的 $m$ 号指令。

分析与解决

一条抛物线可以打到若干只小猪，求至少需要多少条抛物线，这就是题目的核心。不难发现这是经典的重复覆盖问题，可以使用 $DancingLinks$ 求解。但显然这不应该是NOIP提高组的考点，看一看数据范围， $n\le 18$，那就完全可以把小猪进行状态压缩，再 $DP$ 求解。

考虑先预处理抛物线，通过两点确定一条抛物线的方法，也就是说至多会有 $n^2$ 条抛物线，每次先用两个点定一条抛物线，再枚举所有点，把所有位于该条抛物线上的小猪都记录下来，最后用 $path[i][j]=state$ 表示以 第 $i$ 和第 $j$ 个点确定的一条抛物线打过的小猪状态是 $state$。需要注意三个问题：

• 枚举的两个点一定要判断 $x_1\ne x_2$，否则不符合两点定线原则。
• 两点确定的抛物线需要计算系数 $a$ 和 $b$，以便于判断开口问题以及确定某个点是否在抛物线上。如果 $a>0$，则开口朝上是不符合题意的，如果 $a=0$ 那就变成一次函数了（初中数学）。
• 判断大小时要注意一下精度问题，如果两个数的差在一个很小的精度范围内，我们就认为两数相等。

坐标的 $x$ 和 $y$ 值是直接读入的，那如何计算系数 $a$ 和 $b$ 呢？
对于两个坐标分别为 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的点，可以通过抛物线定义式得出：
{ a x 1 2 + b x 1 = y ① a x 2 2 + b x 2 = y ② \left\{

\right. {ax12​+bx1​=y①ax22​+bx2​=y②​
①式两边同时除以 $x_1$，②式两边同时除以 $x_2$，可得，
{ a x 1 + b = y 1 x 1 ③ a x 2 + b = y 2 x 2 ④ \left\{

ax1+b=y1x1③ax2+b=y2x2④" role="presentation" style="position: relative;">ax1+b=y1x1③ax2+b=y2x2④$$\begin{array}{r}a{x}_1+b=\frac{y_1}{x_1}③\\ a{x}_2+b=\frac{y_2}{x_2}④\end{array}$$

\right. ⎩ ⎨ ⎧​ax1​+b=x1​y1​​③ax2​+b=x2​y2​​④​
③－④，得 $a(x_1-x_2)=\frac{y_1}{x_1}-\frac{y_2}{x_2}$，整理为表示 $a$ 的等式为 $a=\frac{\frac{y_1}{x_1}-\frac{y_2}{x_2}}{x_1-x_2}$，通过④式得 $b=\frac{y_1}{x_1}-a{x}_1$.

抛物线预处理完毕后，就要考虑 $DP$ 了，定义 $f[i]$ 为在状态 $i$ 下至少用的抛物线数量。枚举从打到 0 个到打到 $n$ 个的所有状态，每次都寻找当前状态下任意一个还没有被打到的小猪，再让这个点与所有点都做一次状态转移，状态转移方程为：
$$f[i|path[x][j]]=\min (f[i|path[x][j]],f[i]+1)$$
意思就是当前状态与能打到第 $x$ 个点的某条抛物线所对应的状态做并集后所用的抛物线数量与当前状态所用的抛物线数量直接加 1 取较小值。由于是计算最小值，所以要初始化 $f[]$ 的值为无穷大。最后输出时记得减 1，不然你会发现一些很神奇的事情（手动滑稽）。

AC代码

#include 
#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair <double, double> PDD;

const int N = 18, M = 1 << 18;
const double eps = 1e-8; //处理精度问题

int n, m, T;
PDD q[N]; //存储坐标信息
int path[N][N]; //覆盖某两个点的抛物线
int f[M];

//大小比较
int cmp (double x, double y)
{
    if (fabs(x - y) < eps) return 0; //满足精度
    if (x < y) return -1;
    return 1;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
        
        memset(path, 0, sizeof path);
        //预处理抛物线
        for (int i = 0; i < n; i++)
        {
            path[i][i] = 1 << i; //从自身到自身的抛物线
            for (int j = 0; j < n; j++)
            {
                double x1 = q[i].x, y1 = q[i].y;
                double x2 = q[j].x, y2 = q[j].y;
                if (!cmp(x1, x2)) continue; //
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                
                if (cmp(a, 0) >= 0) continue; //不能开口向上
                int state = 0;
                for (int k = 0; k < n; k++)
                {
                    double x = q[k].x, y = q[k].y;
                    if (!cmp(a * x * x + b * x, y)) state += 1 << k;
                }
                path[i][j] = state;
            }
        }
        
        memset(f, 0x3f3f3f3f, sizeof f);
        f[0] = 0;
        for (int i = 0; i < 1 << n; i++)
        {
            int x = 0;
            for (int j = 0; j < n; j++)
            {
                if (!(i >> j & 1))
                {
                    x = j;
                    break;
                }
            } //找一个没有打到的点
            
            for (int j = 0; j < n; j++)
            {
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
            }
        }
        cout << f[(1 << n) - 1] << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84