题面
在坐标系第一象限有一些点，用一些经过原点、开口向下的抛物线 \(y=ax^2+bx\) 覆盖所有点，最少需要多少条
思路
注意到 \(n\le 18\)，基本上是状压 DP
初始做法
考虑压缩点的覆盖状态，设 \(f[S]\) 表示集合 \(S\) 被覆盖需要最少的抛物线数
每两个点确定一条抛物线（经过原点），预处理每条抛物线 \(line_{i,j}\) 能覆盖的点集合
不难得出转移方程： \[
f[S\cup line_{i,j}]=f[S]+1\\
f[S\cup i]=f[S]+1
\] 那么 \(O(2^n)\) 枚举集合状态，再每个状态 \(O(n^2)\) 枚举抛物线转移，复杂度 \(O(Tn^2 2^n)\)
估算一下，计算量在 4e8 级别，不一定过
优化
在每个状态 \(S\)，转移后至少覆盖一个点
从 i 出发枚举抛物线转移和从 j 出发枚举的顺序先后没有关系
先覆盖 i，和覆盖 j 后再覆盖 i，是一样的（如果 j 出发的抛物线能覆盖 i，从 i 出发也一定能覆盖 j）
于是每个状态我只从一个点出发枚举抛物线，复杂度降到 \(O(Tn2^n)\)，稳过
要预处理每个状态最小的未覆盖的点是哪个
提示
从两个点的坐标 \((x_1,y_1),(x_2,y_2)\) 算出抛物线参数 \(a,b\)，要推一下公式：
解 \(a\)： \[
\begin{cases}
y_1=ax_1^2+bx_1\\
y_2=ax_2^2+bx_2
\end{cases}\\
\begin{cases}
\frac{y_1}{x_1}=ax_1+b\\
\frac{y_2}{x_2}=ax_2+b
\end{cases}\\
a(x_1-x_2)=\frac{y_1}{x_1}-\frac{y_2}{x_2}\\
a=\frac{x_2y_1-x_1y_2}{x_1x_2(x_1-x_2)}
\] 解 \(b\)： \[
\begin{cases}
y_1=ax_1^2+bx_1\\
y_2=ax_2^2+bx_2
\end{cases}\\
\begin{cases}
\frac{y_1}{x_1^2}=a+\frac{b}{x_1}\\
\frac{y_2}{x_2^2}=a+\frac{b}{x_2}
\end{cases}\\
b(\frac{1}{x_1}-\frac{1}{x_2})=\frac{y_1}{x_1^2}-\frac{y_2}{x_2^2}\\
b=\frac{x_1^2y_2-x_2^2y_1}{x_1x_2(x_1-x_2)}
\]
code
提交记录
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
| #include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
template<typename T> inline void read(T &x) {}
const int N = 20;
const int MAXN = (1 << 18) - 1;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
struct Line {
double a, b;
bool operator ==(Line &t) {
return fabs(a - t.a) <= eps && fabs(b - t.b) <= eps;
}
};
int T, n, m, maxn;
int low[MAXN], line[N][N], f[MAXN];
double x[N], y[N];
inline Line get_line(int a, int b) {
return (Line){
(x[b] * y[a] - x[a] * y[b]) / (x[a] * x[b] * (x[a] - x[b])),
(x[a] * x[a] * y[b] - x[b] * x[b] * y[a]) / (x[a] * x[b] * (x[a] - x[b]))
};
}
int main() {
for (int i = 0; i <= MAXN; ++i)
for (int j = 0; j < N; ++j)
if ((i & (1 << j)) == 0) {
low[i] = j + 1;
break;
}
read(T);
while (T--) {
read(n), read(m);
maxn = (1 << n) - 1;
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) {
line[i][j] = 0;
if (fabs(x[i] - x[j]) >= eps) {
Line t = get_line(i, j);
if (t.a > -eps) continue;
line[i][j] |= (1 << (i - 1)) | (1 << (j - 1));
for (int k = 1; k <= n; ++k)
if (k != i && k != j && get_line(i, k) == t)
line[i][j] |= 1 << (k - 1);
}
}
for (int i = 0; i <= maxn; ++i) f[i] = INF;
f[0] = 0;
for (int i = 0; i < maxn; ++i) {
int x = low[i], j = 1 << (x - 1);
if (x > n) continue;
f[i|j] = min(f[i|j], f[i] + 1);
for (int y = 1; y <= n; ++y)
f[i|line[x][y]] = min(f[i|line[x][y]], f[i] + 1);
}
printf("%d\n", f[maxn]);
}
return 0;
}
|