题解 | 愤怒的小鸟-NOIP2016提高组复赛

算法知识点: 状态压缩DP

复杂度：

解题思路：

一般抛物线方程：

题目中的抛物线有两个特点：

1. 过原点, 即
2. 开口向下，即

因此抛物线方程为：，有两个未知数，因此两点即可确定一条抛物线。

因此最多有 个不同的抛物线。接下来求出所有不同的抛物线，及其能覆盖的所有点的点集。

此时问题变成了经典的“重复覆盖问题”，即给定01矩阵，要求选择尽量少的行，将所有列覆盖住。

f[i]表示当前已经覆盖的列是i时的最小行数。

转移时随便找到当前未被覆盖的某一列 ，然后枚举所有包含 的行j来选择即可。

即：f[i | j] = min(f[i | j], f[i] + 1)。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 18, M = 1 << N;
const double eps = 1e-6;

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

int cmp(double x, double y)
{
    if (fabs(x - y) <= eps) return 0;
    if (x < y) return -1;
    return 1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);

        for (int i = 0; i + 1 < 1 << n; i ++ )
        {
            for (int j = 0; j < n; j ++ )
                if (!(i >> j & 1))
                {
                    ulowbit[i] = j;
                    break;
                }
        }

        memset(path, 0, sizeof path);

        for (int i = 0; i < n; i ++ )
        {
            path[i][i] = 1 << i;
            for (int j = 0; j < n; j ++ )
            {
                if (!cmp(q[i].x, q[j].x)) continue;
                double x1 = q[i].x, y1 = q[i].y, x2 = q[j].x, y2 = q[j].y;
                double b = (y1 * x2 * x2 / x1 / x1 - y2) / (x2 * x2 / x1 - x2);
                double a = (y1 - b * x1) / x1 / x1;
                if (a > 0) continue;
                int state = 0;
                for (int k = 0; k < n; k ++ )
                {
                    double x = q[k].x, y = q[k].y;
                    if (!cmp(y, a * x * x + b * x)) state += 1 << k;
                }

                path[i][j] = state;
            }
        }

        memset(f, 0x3f, sizeof f);
        f[0] = 0;

        for (int i = 0; i + 1 < 1 << n; i ++ )
        {
            int x = ulowbit[i];
            for (int j = 0; j < n; j ++ )
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }

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

    return 0;
}