Description
有 $n$ 只猪，第 $i$ 只猪在位置 $(x_i, y_i)$ 上，现在你可以用一些鸟来打猪，鸟的飞行轨迹是一个过原点的开口向下的抛物线。问你最少要多少只鸟能打完所有猪。单个测试点内有 $T$ 组数据。
Description
考虑设 $f_{S}$ 表示当前打完状态为 $S$ 的猪的情况下所需要的最少的鸟的数量。
为了方便转移，考虑设 $line_{i, j}$ 表示过猪 $i$ 和猪 $j$ 的抛物线经过的猪的状态。
然后有转移式：
然后你会发现这是 $O(T2^nn^2)$ 的，能不能再快点？
考虑一下，如果当前在状态 $S$ 中有猪 $i$ 没打，那么我现在钦定这次一定打猪 $i$ 其实也是能够取到最优解的，正确性显然。
然后时间复杂度就变成了 $O(T2^nn)$ 的啦！
这题卡精度，eps 建议设成 $10^{-12}∼10^{-6}$。
Solution
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include <cstdio>
#include <cstring>
#define eps 1e-7
#define inf 999999999
#define maxN 18
struct Node{ double x, y; } a[maxN + 10];
int n = 0;
double kA = 0.0, kB = 0.0;
int f[1 << maxN], pow[1 << maxN];
int line[maxN][maxN];
double abs (double x)
{
return x >= 0.0 ? x : (-x);
}
int min (int x, int y)
{
return x < y ? x : y;
}
void work (int A, int B)
{
double Ax = a[A].x * a[A].x, Ay = a[A].x, Az = a[A].y;
double Bx = a[B].x * a[B].x, By = a[B].x, Bz = a[B].y;
double BL = Bx / Ax;
Ax *= BL, Ay *= BL, Az *= BL;
kB = 0.0;
if(abs(By - Ay) > eps)
{
kB = (Bz - Az) / (By - Ay);
}
kA = (Az - Ay * kB) / Ax;
}
int main ()
{
int now = 1;
for(int i = 1;i < maxN; i++)
{
now *= 2;
pow[now] = i;
}
int T = 0;
scanf("%d", &T);
while(T--)
{
scanf("%d %*d", &n);
for(int i = 1;i <= n; i++)
{
scanf("%lf %lf", &a[i].x, &a[i].y);
}
for(int A = 1;A <= n; A++)
{
for(int B = 1;B <= n; B++)
{
line[A][B] = 0;
if(A == B)
{
continue;
}
work(A, B);
if(kA >= 0.0 || abs(kA - 0.0) < eps)
{
continue;
}
for(int i = 1;i <= n; i++)
{
double y = kA * a[i].x * a[i].x + kB * a[i].x;
if(abs(y - a[i].y) <= eps)
{
line[A][B] |= (1 << (i - 1));
}
}
}
}
memset(f, 127 / 3, sizeof(f));
f[0] = 0;
const int maxS = (1 << n) - 1;
for(int S = 0;S < maxS; S++)
{
int x = 0;
for(int i = 1;i <= n; i++)
{
if(!(S & (1 << (i - 1))))
{
x = i;
break;
}
}
for(int i = 1;i <= n; i++)
{
f[S | (1 << (i - 1))] = min(f[S | (1 << (i - 1))], f[S] + 1);
if(x == i)
{
continue;
}
f[S | line[x][i]] = min(f[S | line[x][i]], f[S] + 1);
}
}
printf("%d\n", f[maxS]);
}
return 0;
}
|