「NOIP2016」愤怒的小鸟 - 状压 DP

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

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\) 的小鸟，这样两只猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的猪。

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

数据范围：\(1 \leq n \leq 18\)，\(0 \leq m \leq 2\)，\(0 < x_i, y_i < 10\)，\(1 \leq T \leq 30\)。

解题思路

很明显是状压 DP。先枚举每两个猪是否构成抛物线，以及抛物线后可达到另外的哪些猪。将抛物线可达到的猪的集合存为 \(g_i\)，抛物线个数为 \(\text{sizeG}\)。

接下来我们定义 \(f_i\) 为已清除 \(i\) 集合的猪所需最少的鸟的数量。显然我们可推出下列状态转移方程：

\[ f_{i \cap g_j} = \min\{f_{i \cap g_j}, f_i + 1\} \quad i \in [1, n], j \in [1, \text{sizeG}] \]

初始化 \(f_i = +\infty\)。答案 \(f_S\)，其中 \(S\) 为全集。

代码演示

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
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

const int MAXN = 20;
const double EPS = 1e-6;

inline void solve() {
    int n, m;
    static double x[MAXN], y[MAXN];

    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &x[i], &y[i]);
    }

    if (n == 1) {
        puts("1");
        return;
    }

    static int g[MAXN * MAXN];
    memset(g, 0, sizeof(g));
    int sizeG = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (fabs(x[j] - x[i]) < EPS) continue;
            double a = (x[i] * y[j] - x[j] * y[i]) / (x[i] * x[j] * x[j] - x[i] * x[i] * x[j]);
            double b = (x[i] * x[i] * y[j] - x[j] * x[j] * y[i]) / (x[i] * x[i] * x[j] - x[i] * x[j] * x[j]);
            if (a > -EPS) continue;

            for (int k = 0; k < n; k++) {
                if (fabs(a * x[k] * x[k] + b * x[k] - y[k]) < EPS) {
                    g[sizeG] |= (1 << k);
                }
            }
            sizeG++;
        }
    }

    static int f[1 << MAXN];
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i < n; i++) f[1 << i] = 1;
    f[0] = 0;

    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < sizeG; j++) {
            f[i | g[j]] = std::min(f[i | g[j]], f[i] + 1);
        }
        for (int j = 0; j < n; j++) {
            f[i | (1 << j)] = std::min(f[i | (1 << j)], f[i] + 1);
        }
    }

    printf("%d\n", f[(1 << n) - 1]);
}

int main() {
    int t;

    scanf("%d", &t);

    while (t--) solve();

    return 0;
}