愤怒的小鸟
题目来源
NOIP 2016 D2T3
题目描述
在一个二维平面上，有一只小鸟在
(
0
,
0
)
\ (0,\ 0)
(0, 0) 处，有
n
\ n
n 只小猪在
(
x
i
,
y
i
)
\ (x_i,\ y_i)
(xi, yi) 处。小鸟可以以
y
=
a
x
2
+
b
x
(
a
<
0
)
\ y=ax^2+bx\ (a<0)
y=ax2+bx (a<0) 的抛物线的飞出，并消灭在它飞行路径上的所有小猪。求小鸟至少要飞几次才可以消灭所有的小猪。包含多组测试数据。
n
≤
18
,
T
≤
30
,
x
i
,
y
i
∈
d
o
u
b
l
e
\ n\leq 18,\ T\leq 30,\ x_i,y_i\in double
n≤18, T≤30, xi,yi∈double
解题方法
方法一 (朴素版)
还是状压DP，可以直接一维，定义
f
s
\ f_s
fs 表示消灭状态为
s
\ s
s 时小鸟飞的最少次数。
如果直接暴力状压的话时间复杂度为
O
(
T
n
3
2
n
)
\ O(Tn^32^n)
O(Tn32n) ，因为还要枚举
a
,
b
\ a,\ b
a, b ，显然是不可以接受的。
方法二 (AC版)
推式子
假设现在有两点
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
\ (x_1,\ y_1),\ (x_2,\ y_2)
(x1, y1), (x2, y2) ，那么代入
y
=
a
x
2
+
b
x
\ y=ax^2+bx
y=ax2+bx 实在是做不了，下面给出推导为
a
,
b
\ a,\ b
a, b 的式子：
{
x
1
2
a
+
x
1
b
=
y
1
x
2
2
a
+
x
2
b
=
y
2
→
{
x
1
2
x
2
a
+
x
1
x
2
b
=
x
2
y
1
x
1
x
2
2
a
+
x
1
x
2
b
=
x
1
y
2
→
a
=
x
2
y
1
−
x
1
y
2
x
1
2
x
2
−
x
1
x
2
2
→
a
=
y
1
x
1
−
y
2
x
2
x
1
−
x
2
,
b
=
y
1
x
1
−
a
x
1
\left\{\begin{matrix} x_1^2a+x_1b=y_1\\ x_2^2a+x_2b=y_2 \end{matrix}\right. \to \left\{\begin{matrix} x_1^2x_2a+x_1x_2b=x_2y_1\\ x_1x_2^2a+x_1x_2b=x_1y_2 \end{matrix}\right. \to a=\frac{x_2y_1-x_1y_2}{x_1^2x_2-x_1x_2^2} \to a=\frac{\frac{y_1}{x_1}-\frac{y_2}{x_2}}{x_1-x_2} ,\ b=\frac{y_1}{x_1}-ax_1
{x12a+x1b=y1x22a+x2b=y2→{x12x2a+x1x2b=x2y1x1x22a+x1x2b=x1y2→a=x12x2−x1x22x2y1−x1y2→a=x1−x2x1y1−x2y2, b=x1y1−ax1
但是，并不是所有的
x
1
,
x
2
,
y
1
,
y
2
\ x_1,\ x_2,\ y_1,\ y_2
x1, x2, y1, y2 都可以形成二次函数，
x
1
≠
x
2
\ x_1\neq x_2
x1=x2 才可以，因为没有两点在一条抛物线上绝对垂直。
题目要求
a
<
0
\ a<0
a<0 ，要特判。
定义
和朴素做法一样，定义
f
s
\ f_s
fs 表示消灭状态为
s
\ s
s 时最少需要发射的小鸟数。
但是，不同处在于，可以预处理
f
l
y
i
,
j
\ fly_{i,\ j}
flyi, j 。
定义
f
l
y
i
,
j
\ fly_{i,\ j}
flyi, j 为小猪
i
\ i
i 和小猪
j
\ j
j 能组成的抛物线所能经过的其它小猪，需要注意的是
f
l
y
\ fly
fly 存的是一个状态。
举个例子：
如果
i
,
j
\ i,\ j
i, j 的抛物线经过
k
\ k
k ，则
f
l
y
i
,
j
=
f
l
y
i
,
j
∣
2
k
−
1
\ fly_{i,\ j}=fly_{i,\ j}|2^{k-1}
flyi, j=flyi, j∣2k−1
状态转移
先给出循环框架：
for (int s = 0; s < (1 << n); s++)
for (int i = 1; i <= n; i++)
if (!(s & (1 << (i - 1)))) //抛物线上的点必须没有被消灭过
for (int j = 1; j <= n; j++) {
...
}
然后要分情况讨论：
-
i
=
j
\ i=j
i=j ，这种情况表示只消灭掉一只，可能是因为剩下的所有都有同一横坐标或者只有一只了。
则f
s
∣
2
i
−
1
=
m
i
n
(
f
s
∣
2
i
−
1
,
f
s
+
1
)
\ f_{s|2^{i-1}}=min(f_{s|2^{i-1}},\ f_s+1)
fs∣2i−1=min(fs∣2i−1, fs+1) 。
要么利用已经计算过的最小值，要么新开一条抛物线。 -
i
≠
j
\ i\neq j
i=j ，这种情况表示消灭两只及以上。一条抛物线肯定能消灭两只，至于更多只就看造化了。
则f
s
∣
f
l
y
i
,
j
=
m
i
n
(
f
s
∣
f
l
y
i
,
j
,
f
s
+
1
)
\ f_{s|fly_{i,\ j}}=min(f_{s|fly_{i,\ j}},\ f_s+1)
fs∣flyi, j=min(fs∣flyi, j, fs+1) 。
以下为核心代码：
for (int s = 0; s < (1 << n); s++)
for (int i = 1; i <= n; i++)
if (!(s & (1 << i - 1))) {
for (int j = 1; j <= n; j++) {
if (i == j) f[s | 1 << (i - 1)] = min(f[s | 1 << (i - 1)], f[s] + 1);
if (fabs(x[i] - x[j]) < eps) continue;
f[s | fly[i][j]] = min(f[s | fly[i][j]], f[s] + 1);
}
break; //剪枝，两点的先后顺序不影响结果
}
这样的话，通过预处理，时间复杂度降至
O
(
T
(
n
3
+
n
2
2
n
)
)
\ O(T(n^3+n^22^n))
O(T(n3+n22n)) ，约等于
T
n
2
2
n
\ Tn^22^n
Tn22n ，但是容易被卡常，但是在
n
2
2
n
\ n^22^n
n22n 中有许多状态在集合中，所以已经删掉了许多状态，总体时间可以接受。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
const double eps = 1e-7;
int T;
int f[1 << N];
int fly[N][N];
double x[N], y[N];
inline int read()
{
register int sum = 0, w = 1; register char ch = getchar();
while (ch < '0' or ch > '9') { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= '0' and ch <= '9') { sum = sum * 10 + ch - '0'; ch = getchar(); }
return sum * w;
}
int main()
{
T = read();
while (T--) {
memset(fly, 0, sizeof fly);
memset(f, 0x3f, sizeof f);
int n = read(), m = read();
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &x[i], &y[i]);
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++) {
if (fabs(x[i] - x[j]) < eps) continue; //x1, x2坐标不能相同
double a = (y[i] / x[i] - y[j] / x[j]) / (x[i] - x[j]);
if (a >= 0) continue;
double b = y[i] / x[i] - a * x[i];
for (int k = 1; k <= n; k++)
if (fabs(y[k] / x[k] - (a * x[k] + b)) < eps) fly[i][j] |= 1 << k - 1;
}
f[0] = 0;
for (int s = 0; s < (1 << n); s++)
for (int i = 1; i <= n; i++)
if (!(s & (1 << i - 1))) {
for (int j = 1; j <= n; j++) {
if (i == j) f[s | 1 << (i - 1)] = min(f[s | 1 << (i - 1)], f[s] + 1);
if (fabs(x[i] - x[j]) < eps) continue;
f[s | fly[i][j]] = min(f[s | fly[i][j]], f[s] + 1);
}
break;
}
printf("%d\n", f[(1 << n) - 1]);
}
return 0;
}