UOJ 265

题解

考虑状态压缩 DP。设 $f(S)$ 为消灭集合 $S$ 中所有小猪需要的最少发射次数,考虑一次攻击的方式,有转移方程
$$f(S) = min\{min\{f(S \setminus \{i\}) | i \in S\}, min\{f(S \setminus target(i, j) | i, j \in S)\}\} + 1$$
其中 $target(i, j)$ 表示经过小猪 $i, j$ 的抛物线所经过的小猪的集合(若抛物线的 $a < 0$ 则为 $\varnothing$ )。由于集合的差运算难以高效实现,可以使用以下等价形式:
$$f(S) = min\{min\{f(S \setminus \{i\}) | i \in S\}, min\{f(S \cap left(i, j) | i, j \in S)\}\} + 1$$
其中 $left(i, j) = U \setminus target(i, j)$ ,$U$ 为所有小猪的集合。$left$ 的值可以用 $O(n^3)$ 的时间预处理,每次转移枚举 $i, j$ 是 $O(n^2)$ 的,状态数为 $2^n$,总的复杂度是 $O(n^2 2^n)$。
事实上,该方程可以写为
$$f(S) = min\{f(S \setminus \{min\ S\}), min\{f(S \cap left(\min\ S, i) | i \in S, i \neq min\ S)\}\} + 1$$
其中 $min\ S$ 表示 $S$ 中编号最小的小猪。事实上,上式中的 $min\ S$ 可以用 S 中的任何一个小猪代替。该方程的正确性源于以下结论:

定义 $S$ 的方案是一个抛物线的集合,使得射出这些抛物线能消灭 $S$ 中所有小猪,$S$ 的包含的抛物线最少的方案称为 $S$ 的最优方案,则

  • 对于任何 $i \in S$,$S$ 的任何最优方案 $T$ 中一定存在一条经过 $i$ 的抛物线
  • 对于 $S$ 的任何最优方案 $T$,任何抛物线 $k \in T$ 都使得 $T \setminus \{k\}$ 是 $S \setminus left(k)$ 的最优方案

后一个结论使方程满足了最优子结构性质(感谢 lhy 指出),因此 $f(S)$ 必然可以从上述的一个 $S \setminus left(k)$ 的状态转移来。前一个结论是显然的,接下来证明后一个结论。设 $T$ 是 $S$ 的一个最优方案,假设 $k \in T$ 使得 $S \setminus left(k)$ 有比 $T \setminus \{k\}$ 更优的方案 $R$,则 $R \cup \{k\}$ 是 $S$ 的一个方案,且比 $T$ 更优,这与 $T$ 是 $S$ 的最优方案矛盾,所以后一个结论成立。
优化后的转移是 $O(n)$ 的,总的复杂度是 $O(n 2^n)$ ,可以通过。

代码

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
#include <cstdio>
#include <cmath>
#include <algorithm>
const int MAXN = 20, INF = 0x3f3f3f3f;
const double EPS = 1e-7; // **
int n, m, dp[1048580], left[MAXN][MAXN];
double x[MAXN], y[MAXN];
inline int dcmp(const double &a, const double &b) { // *****
return (fabs(a - b) < EPS) ? 0 : ((a < b) ? -1 : 1);
}
inline bool in(const int &a, const int &s) {
return (s >> a) & 1;
}
int main() {
int t, i, j, k, s, u;
double a, b;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
u = (1 << n) - 1;
for (i = 0; i < n; ++i)
scanf("%lf%lf", x + i, y + i);
for (i = 0; i < n; ++i) {
for (j = i + 1; j < n; ++j) {
int &ki = left[i][j];
a = ((y[i] / x[i]) - (y[j] / x[j])) / (x[i] - x[j]);
if (dcmp(a, 0) != -1) {
ki = u;
continue;
}
b = y[i] / x[i] - a * x[i];
ki = 0;
for (k = 0; k < n; ++k) {
if (dcmp(a * x[k] * x[k] + b * x[k], y[k]) != 0)
ki |= 1 << k; // **
}
}
}
dp[0] = 0;
for (s = 1; s <= u; ++s) {
dp[s] = INF;
for (i = 0; !in(i, s); ++i);
dp[s] = std::min(dp[s], dp[s ^ (1 << i)] + 1);
for (j = i + 1; j < n; ++j)
if (in(j, s))
dp[s] = std::min(dp[s], dp[s & left[i][j]] + 1);
}
printf("%d\n", dp[u]);
}
return 0;
}