题解

思路分析

这是一道结合状态压缩DP和枚举抛物线的经典问题。

问题建模

• 给定平面上 $n$ 个点（猪的位置）
• 每只小鸟的轨迹是形如 $y = ax^2 + bx$ 的抛物线（$a < 0$）
• 求最少需要多少只小鸟消灭所有猪

核心思路

1. 抛物线的确定

两个不同的点可以唯一确定一条过原点的抛物线 $y = ax^2 + bx$。

给定点 $(x_1, y_1)$ 和 $(x_2, y_2)$，可以解方程组：

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

解得：

$$a = \frac{x_2y_1 - x_1y_2}{x_1x_2(x_1-x_2)}, \quad b = \frac{x_1^2y_2 - x_2^2y_1}{x_1x_2(x_1-x_2)} $$

需要满足 $a < 0$（抛物线开口向下）。

2. 预处理所有可能的抛物线

用二进制状态 line[i][j] 表示过点 $i$ 和点 $j$ 的抛物线能覆盖哪些猪（用状压表示）。

对于每对点 $(i, j)$：

• 计算出 $a$ 和 $b$
• 检查所有其他点是否在这条抛物线上（考虑浮点误差）
• 用二进制数记录覆盖的猪的集合

3. 状态压缩DP

定义 $dp[S]$ 表示消灭状态 $S$ 中的所有猪所需的最少小鸟数。

状态转移：

• 对于当前状态 $S$，找到第一个还未被消灭的猪 $i$
• 枚举所有经过猪 $i$ 的抛物线（可能过单个猪或两个猪）
• 对于每条抛物线覆盖的猪的集合 $mask$：$$dp[S] = \min(dp[S], dp[S \setminus mask] + 1)$$

其中 $S \setminus mask$ 表示从状态 $S$ 中去掉 $mask$ 覆盖的猪。

4. 优化技巧

• 枚举顺序优化：每次找到状态中最低位的 $1$（第一个未消灭的猪），只枚举经过它的抛物线
• 单猪抛物线：即使一条抛物线只过一个猪，也要考虑（对应只消灭一只猪的情况）

算法步骤

1. 预处理阶段：

   • 枚举所有点对 $(i, j)$，计算抛物线参数
   • 判断 $a < 0$ 是否满足
   • 检查所有点，得到每条抛物线的覆盖集合

2. DP阶段：

   • 初始化：$dp[0] = 0$，其余为 $\infty$
   • 枚举状态 $S$ 从 $1$ 到 $2^n - 1$
   • 找到 $S$ 中第一个为 $1$ 的位（猪 $i$）
   • 枚举所有经过猪 $i$ 的抛物线，更新 $dp[S]$

3. 答案：$dp[2^n - 1]$

复杂度分析

• 预处理抛物线：$O(n^3)$（枚举点对 + 检查所有点）
• DP：$O(2^n \cdot n^2)$
• 总时间复杂度：$O(2^n \cdot n^2 + n^3)$
• 空间复杂度：$O(2^n + n^2)$

由于 $n \leq 18$，$2^{18} = 262144$ 可以接受。

#include<bits/stdc++.h>
using namespace std;
int n, ans;
double A[20], B[20], X[20], Y[20];
bool eq(double a, double b)
{
	return abs(a - b) < 1e-8;
}
void dfs(int id, int s)
{
	int sum = s;
	for (int i = 1;i < id;i++)
	{
		if (eq(A[i], 0))
		{
			sum++;
		}
	}
	if (sum >= ans)
	{
		return;
	}
	if (id > n)
	{
		ans = sum;
		return;
	}
	for (int i = 1;i < id;i++)
	{
		if (!eq(A[i], 0.0) && eq(A[i] * X[id] * X[id] + B[i] * X[id], Y[id]))
		{
			A[id] = A[i];
			B[id] = B[i];
			dfs(id + 1, s);
			return;
		}
		if (A[i] == 0.0)
		{
			double d = X[i] * X[id] * (X[i] - X[id]);
			if (!eq(d, 0))
			{
				double k1 = (X[id] * Y[i] - X[i] * Y[id]) / d, k2 = (X[i] * X[i] * Y[id] - X[id] * X[id] * Y[i]) / d;
				if (k1 < 0)
				{
					A[i] = A[id] = k1;
					B[i] = B[id] = k2;
					dfs(id + 1, s + 1);
					A[i] = B[i] = 0.0;
 				}
			}
		}
	}
	A[id] = B[id] = 0.0;
	dfs(id + 1, s);
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int u;
		cin >> n >> u;
		memset(A, 0, sizeof(A));
		memset(B, 0, sizeof(B));
		memset(X, 0, sizeof(X));
		memset(Y, 0, sizeof(Y));
		for (int i = 1;i <= n;i++)
		{
			cin >> X[i] >> Y[i];
		}
		ans = 1e9;
		dfs(1, 0);
		cout << ans << endl;
	}
}

题解

「愤怒的小鸟」要用尽量少的抛物线把所有的猪覆盖。
每条抛物线形如：

$$y = a x^2 + b x$$

并要求 $a < 0$（弹道必须向下开口）。思路是回溯枚举：

1. 按输入顺序逐个处理点。数组 $A[i]$、$B[i]$ 记录点 $i$ 所在抛物线的系数，$0$ 表示尚未分配。
2. 对当前点，若前面已存在抛物线且它能满足$$a x_i^2 + b x_i = y_i$$ 则直接沿用该抛物线。
3. 否则尝试与以前尚未建线的点两两配对。由两点坐标可以解出唯一的 $a,b$，只有当 $a < 0$ 时才是合法轨迹。临时把这两点分配到新抛物线并继续递归。
4. 如果以上都不行，则把当前点单独留到后面（表示“这个点还没打”），继续递归。
   $sum$ 统计当前已经新建的抛物线数量，若 $sum \ge ans$（当前最优）就剪枝。

搜索结束时的最小 $ans$ 即为答案。由于 $n \le 18$，回溯结合剪枝就能通过。

#include<bits/stdc++.h>
using namespace std;
int n, ans;
double A[20], B[20], X[20], Y[20];
bool eq(double a, double b)
{
	return abs(a - b) < 1e-8;
}
void dfs(int id, int s)
{
	int sum = s;
	for (int i = 1;i < id;i++)
	{
		if (eq(A[i], 0))
		{
			sum++;
		}
	}
	if (sum >= ans)
	{
		return;
	}
	if (id > n)
	{
		ans = sum;
		return;
	}
	for (int i = 1;i < id;i++)
	{
		if (!eq(A[i], 0.0) && eq(A[i] * X[id] * X[id] + B[i] * X[id], Y[id]))
		{
			A[id] = A[i];
			B[id] = B[i];
			dfs(id + 1, s);
			return;
		}
		if (A[i] == 0.0)
		{
			double d = X[i] * X[id] * (X[i] - X[id]);
			if (!eq(d, 0))
			{
				double k1 = (X[id] * Y[i] - X[i] * Y[id]) / d, k2 = (X[i] * X[i] * Y[id] - X[id] * X[id] * Y[i]) / d;
				if (k1 < 0)
				{
					A[i] = A[id] = k1;
					B[i] = B[id] = k2;
					dfs(id + 1, s + 1);
					A[i] = B[i] = 0.0;
 				}
			}
		}
	}
	A[id] = B[id] = 0.0;
	dfs(id + 1, s);
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int u;
		cin >> n >> u;
		memset(A, 0, sizeof(A));
		memset(B, 0, sizeof(B));
		memset(X, 0, sizeof(X));
		memset(Y, 0, sizeof(Y));
		for (int i = 1;i <= n;i++)
		{
			cin >> X[i] >> Y[i];
		}
		ans = 1e9;
		dfs(1, 0);
		cout << ans << endl;
	}
}