愤怒的小鸟（集合性状压dp）
题目链接： 524. 愤怒的小鸟 - AcWing题库
在题目条件下，两个点可以确定一条过原点的抛物线，有n个点，那么就可以预处理出n^2条抛物线，然后再预处理出每条抛物线最多经过多少个点，以及是哪些点。
这是一个重复覆盖问题，与之相对的就是精确覆盖问题；
这两个问题都已经有的最优解法：dancing links 这是一种数据结构（十字链表），可以优化dfs爆搜；
但是dancing links没学，这里用状压dp去达到相似的效果，优化爆搜；
爆搜的核心是：顺序，要以那种顺序枚举所有方案。以爆搜为基础思考优化方案；
优化方法：记忆化搜索（状压dp），注意到每一个state传入dfs函数都会唯一对应一个res解，因此我们可以使用一个f[state]将其存储下来避免重复计算。
x代表为当前state中未被覆盖的一列，path表示一条可以覆盖当前列的抛物线，new_state就可以用上述的公式求得。
两个过程的区别就是引入状压dp之后，有些已经被计算过的state再dfs再次遇到的时候不会被重复再计算一遍，大概可以优化一半多。
f中存储的就是当前状态下最少的抛物线数；
遇到相同的状态但是线数更多的时候就会被直接排除掉；
看看拦截导弹那一题；
path i, j 表示由第i个与第j个猪创建的抛物线经过了那些猪，使用二进制表示。
最后再总结一下这道题目的思路：
-
使用pair读入个点；
-
利用任意两个点的位置求出抛物线集合path i, j i与j代表选择了第i和j个点，path中存储的是其经过的所有猪的二进制表达；
-
设置f为0x3f，f0 为0；
-
枚举所有的当前猪的位置情况（二进制）i，循环每一种情况中没有被干掉的猪x，枚举所有包含这个猪的抛物线path x, j，那么最终的状态转移方程就是：
f[i | path[x][j]] = min(f[i | path[i][j]], f[i]+1)这样的状态转移方程的思想就是，将每一个f通过可以由哪一条合法的抛物线转移过来进行状态划分；所以这里以终点进行枚举，因为通过终点反推其组合时困难的；
但是这里可以不采用集合的思想，将这道题看作一种记忆化搜索可以更便于你的理解；
看一下如果爆搜当前任意一个抛物线时是否有更好的选择（f中的min），否则就将f更新为
f[i] + 1，这样当就可以减去不必要的分枝，不行的转移方案直接剪掉，减少搜索花费； -
另外需要注意一点，double比较的时候有可能出现误差，需要自己再写一个cmp函数用于比较；
-
fabs函数用于求浮点数的绝对值；
代码如下：
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 18, M = 1 << 18;
const double eps = 1e-8; //这里
PDD q[N];
int n, m;
int f[M];
int path[N][N];
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--)
{
cin>>n>>m;
for(int i=0; i<n; i++)
cin>>q[i].x>>q[i].y;
memset(path, 0, sizeof path); //记得每一次都要恢复原样
for(int i=0; i<n; i++)
{
path[i][i] = 1 << i;//防一手只给一个点的情况
for(int j=0; j<n; j++)
{
double x1 = q[i].x, y1 = q[i].y;
double x2 = q[j].x, y2 = q[j].y;
if(!cmp(x1, x2)) continue; // 在同一列的两个点不能作为构建抛物线的点
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;
//if(a > 0) continue; 这个写法被坑了一手
if(cmp(a, 0) >= 0) continue;
int state = 0;
for(int k=0; k<n; k++)
{
double x3 = q[k].x, y3 = q[k].y;
if(!cmp(a* x3 * x3 + b * x3, y3)) state += 1 << k;
}
path[i][j] = state; //全部抛物线预处理完成；
}
}
memset(f, 0x3f, sizeof f); //求最小值，初始化为inf；
f[0] = 0; //一只猪没杀需要的抛物线数为0
for(int i=0; i+1 < 1 << n; i++) //dp基操，上来先将f的每一维按照一定顺序枚举一遍；同时全为1的状态不需要枚举，
{ //因为就是答案，后面已经计算出来了
int x = 0;
for(int j=0; j<n; j++)//检查一下哪一位为空
{
if((i >> j & 1) == 0)
{
x = j;
break;
}
}
for(int j=0; j<n; j++)
{
f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1); //多思考一下这个状态转移方程是怎么来的
}
}
cout<<f[(1 << n) - 1]<<endl;
}
return 0;
}