愤怒的小鸟
Kiana最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。 有一架弹弓位于处，每次可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如的曲线，其中 是 Kiana指定的参数，且必须满足。
当小鸟落回地面(即轴)时，它就会瞬间消失。
在游戏的某个关卡里，平面的第一象限中有只绿色的小猪，其中第只小猪所在的坐标为。
如果某只小鸟的飞行轨迹经过了，那么第只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行;
如果一只小鸟的飞行轨迹没有经过，那么这只小鸟飞行的全过程就不会对第只小猪产生任何影响 。例如，若两只小猪分别位于和，Kiana可以选择发射一只飞行轨迹为的小鸟，这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个这个游戏。
这些指令将在输入格式中详述。
假设这款游戏一共有T个关卡，现在Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。
由于她不会算，所以希望由你告诉她。
输入格式
第一行包含一个正整数，表示游戏的关卡总数。下面依次输入这个关卡的信息。 每个关卡第一行包含两个非负整数，分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。 接下来的行中，第行包含两个正实数，表示第只小猪坐标为，数据保证同一个关卡中不存在两只坐标完全相同的小猪。 如果，表示 Kiana输入了一个没有任何作用的指令。 如果，则这个关卡将会满足:至多用只小鸟即可消灭所有小猪。 如果，则这个关卡将会满足:一定存在一种最优解，其中有一只小鸟消灭了至少只小猪。 保证，输入中的实数均保留到小数点后两位。
上文中，符号和分别表示对c向上取整和向下取整，例如︰ 。
思路
给你一个第一象限的坐标系, 里面有个点, 求可以用多少个抛物线, 把所有点覆盖掉。
抛物线有无限多个, 而我们需要找到的是能够覆盖至少一个点的抛物线, 然后再从之中找出最小使用数量。 爆搜就是用一定顺序枚举所有情况。
利用爆搜解决重复覆盖问题：
void dfs(int state, int cnt)
{
if(state 已经包含所有列) ans = min(cnt, ans); return;
任选没有被覆盖的一列x:
枚举所有能覆盖x的抛物线：
更新一下state->new_state
dfs(new_state, cnt + 1);
}这里使用记忆化搜索, 将已经计算的state存下来。
更新时为：f[state] = f[path[x][y]]
如何求能覆盖到x的抛物线呢？
两个点
转换一下为：
相减即可得出a：
回代即可得出b：
通过枚举任意两点可以确定最多个抛物线, 且满足
对于每个抛物线有可能会经过其他点, 故再枚举所有点将能覆盖到的加入
这样预处理的时间复杂度为
状态表示： f[state] 当前所有点的覆盖状态为state, 所用的抛物线数量（state是二进制压缩储存的点集覆盖状态）
状态计算：
f[new_state] = min(f[state] + 1) new_state即为用新抛物线覆盖之后的点集覆盖情况
这里的DP顺序为刷表法, 即枚举所有当前能走到的新状态然后更新
一些小问题： 这里需要用到浮点数计算, 且在判断某个点是否会被抛物线覆盖时会判断相等。 浮点数储存时是有误差的, 故需要自己手写一个判断函数, 忽略掉一定误差后判断。
const double eps = 1e-6;
int cmp(double a, double b)
{
if(fabs(a - b) < eps) return 0;
if(a > b) return 1;
return -1;
}#include <iostream>
#include <cstring>
#include <cmath>
#define x first
#define y second
using namespace std;
const int N = 20, M = 1 << 18, INF = 0x3f3f3f3f;
const double eps = 1e-6;
typedef pair<double, double> PDD;
int f[M];
PDD point[N];
int path[N][N];
int n,m;
int cmp(double a, double b)
{
if(fabs(a - b) < eps) return 0;
if(a > b) return 1;
return -1;
}
int main()
{
int T;
cin >> T;
while(T--)
{
memset(f, 0x3f, sizeof f);
memset(path, 0, sizeof path);
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> point[i].x >> point[i].y;
for(int i = 0; i < n; i++)
{
path[i][i] = 1 << i;
for(int j = 0; j < n; j++)
{
double x1 = point[i].x, y1 = point[i].y;
double x2 = point[j].x, y2 = point[j].y;
if(!cmp(x1,x2)) continue;
double a = (y1/x1 - y2/x2)/(x1-x2);
double b = y1/x1 - a*x1;
if(cmp(a,0.0) >= 0) continue;
path[i][j] = (1 << i) + (1 << j);
for(int k = 0; k < n; k++)
{
x1 = point[k].x, y1 = point[k].y;
if(k != i && k != j && !cmp(a*x1*x1 + b*x1, y1))
path[i][j] += 1 << k;
}
}
}
int res = INF;
f[0] = 0;
for(int i = 0; i + 1 < 1 << n; i++)
{
int t = -1;
for(int k = 0; k < n; k++)
if(!(i >> k & 1))
{
t = k;
break;
}
for(int k = 0; k < n; k++)
{
int new_state = path[t][k] | i;
f[new_state] = min(f[new_state], f[i] + 1);
}
}
cout << f[(1 << n) - 1] << endl;
}
return 0;
}