Description

题目链接

题目大意：多测，用最少的过原点且开口向下的抛物线覆盖平面上的 $n$ 个点。$1 \le n \le 18$。

Solution

考虑状压 DP，设 $f(S)$ 表示覆盖 $S$ 中所有点需要的最少抛物线个数。

设 $x, y \in S$，那么 $f(S) = \min f(S - \{x, y\}) + 1, f(0) = 0$（这个方程并不完全正确）。

注意到经过 $x, y$ 的抛物线可能也经过了其他点，因此我们需要求出任意两点确定的抛物线能覆盖多少点。

在这里涉及到一个求抛物线的方法：已知 $y = ax^2 + bx$ 过 $(x_1, y_1), (x_2, y_2)$，求 $a, b$。

看了眼题解好像没有跟我做法一样的。

$$ \begin{cases}ax_1^2 + bx_1 = y_1\\ax_2^2 + bx_2 = y_2\end{cases} $$

将两式分别同时除以 $x$，然后相减即可得到 $a$，再之后代入得到 $b$。我觉得这种方法比矩阵要好想多了。

确定 $a, b$ 以后只需要 $O(n ^ 3)$ 暴力求经过哪些点即可。这里设 $w(i, j)$ 表示经过 $i, j$ 的抛物线能覆盖的点的集合。

接下来直接 DP。由于抛物线可能经过多个点，使用刷表法会方便一些，用 $f(S)$ 去更新 $f(S \cup w(i, j))$。

问题来了，枚举两个点是平方的，枚举集合是指数级的，时间复杂度为 $O(2^n n^2)$，再加上这题是多测，很难拿到满分。

注意到如果 $S$ 的某一位为 $0$，那么这一位终究会变为 $1$。我们直接钦定这一位作为 $i$，然后枚举 $j$，这样就变成 $O(n)$ 的了。找这一位可以在程序的开头预处理。

于是时间复杂度被我们优化成了 $O(2^n n)$。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

const double eps = 1e-8;

double x[20], y[20];
double a, b;
int w[20][20];
int f[1 << 20], g[1 << 20];
int T, n, m;

inline void solve(int i, int j) {
    a = (y[i] / x[i] - y[j] / x[j]) / (x[i] - x[j]);
    b = (y[i] - a * x[i] * x[i]) / x[i];
    return ;
}

double fabs(double x) { return x < 0 ? -x : x; }

int main() {
    for (int i = 0; i < (1 << 18); ++i) {
        int j = 1;
        while (j <= 18 && (i & (1 << (j - 1))))    ++j;
        g[i] = j;
    }
    read(T);
    while (T--) {
        read(n), read(m);
        memset(w, 0, sizeof(w));
        memset(f, 0x3f3f3f3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= n; ++i)    scanf("%lf %lf", &x[i], &y[i]);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (fabs(x[i] - x[j]) < eps)    continue;
                solve(i, j);
                if (a > -eps)    continue;
                for (int k = 1; k <= n; ++k) {
                    if (fabs(a * x[k] * x[k] + b * x[k] - y[k]) < eps) {
                        w[i][j] |= (1 << (k - 1));  
                    }  
                }
            }
        }
        for (int i = 0; i < (1 << n); ++i) {
            int j = g[i];
            f[i | (1 << (j - 1))] = std::min(f[i | (1 << (j - 1))], f[i] + 1);
            for (int k = 1; k <= n; ++k)    f[i | w[j][k]] = std::min(f[i | w[j][k]], f[i] + 1);
        }
        printf("%d\n", f[(1 << n) - 1]);
    }
    return 0;
}