关键：枚举所有的情况会超时，只需要枚举必要的中间状态，使得结果正确即可
步骤：
- 预处理出所有的抛物线
- 状态压缩dp
分析：
由于抛物线一定通过原点(0,0),任意两个小猪的坐标都可以组成一个抛物线
- 开头向上? (a<0)
- 经过原点（0，0）
- 只有一个点时，可以看成直线
同时，由于任意两个点之间是构成抛物线的，并且一条抛物线上可能有多个小猪
- 一条抛物线上有多个小猪
- 两个点x不能相同，否则够不成抛物线
那么，有两个点可以推出抛物线的公式为
? ? ? ? ? ? ? ? ? ??
- 由于是浮点数，浮点数的比较要使用cmp函数
暴力搜索：
先处理出所有的抛物线，记录当前状态state
void dfs(int state,int now)
{
//找到第一个没有覆盖的点
for(...)
...
//根据这个点进行dfs,枚举所有这个点所在的抛物线,看看哪个合适
for()
dfs(state|...,now+1)
}状态压缩：
由于点的范围很小，可以先预处理出所有的点，然后进行状态压缩dp
状态表示：所有当前已覆盖点的状态为i的所有集合
状态计算：
x表示当前没有覆盖的某个点，k表示包括x在内的所有点，运用正拓扑排序的方式进行递推
- dp[i|p[x][k]]=min(dp[i]+1)
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 19, M = 1 << 19;
double eps = 1e-6;
int dp[M];
typedef pair<double, double> PII;
PII q[N];
int p[N][N];
int cmp(double a, double b)
{
if (abs(a - b) < eps) return 0;
if (a > b) return 1;
return -1;
}
void solve()
{
int n, m;
cin >> n >> m;
memset(dp, 0x3f, sizeof dp);
//预处理
for (int i = 0;i < n;i++)
cin >> q[i].x >> q[i].y;
memset(p,0,sizeof p);
for (int i = 0;i < n;i++)
{
p[i][i] = 1 << i;
for (int j = 0;j < n;j++)
{
if (!cmp(q[i].x, q[j].x)) continue;
int state = 0;
double x1 = q[i].x, y1 = q[i].y;
double x2 = q[j].x, y2 = q[j].y;
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;
if(a>=0) continue;
//寻找所有在一条线上的点
for (int k = 0;k < n;k++)
{
double x = q[k].x, y = q[k].y;
if (!cmp(a * x * x + b * x, y))
state += 1 << k;
}
p[i][j] = state;
}
}
//状态压缩dp枚举
dp[0] = 0;
for (int i = 0;i + 1 < 1 << n;i++)
{
int x = -1;
for (int j = 0;j < n;j++)
if ((i >> j & 1) == 0)
{
x = j;
for (int k = 0;k < n;k++)
dp[i | p[x][k]] = min(dp[i | p[x][k]], dp[i] + 1);
}
}
cout << dp[(1 << n) - 1] << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}优化版本
由于我们发现，对于某一个抛物线，他之前用过的抛物线，和后面用的抛物线没有任何关系
那么我们可以抛弃一些中间状态，不去计算他，只要确保最终状态dp[(1<<n)-1]的正确
那么我们不需要记录 0~1<<n -1 中的所有状态，只需要确保 0~n-1 所有的点，都能够使用到包含他本身的，最优的抛物线。
那么我们可以从0~1<<n-1 递推 ,然后每次找到第一个未覆盖的点(任意一个都可以)，然后根据这个点枚举所有他所在的抛物线，看看哪个对于当前状态最佳进行递推
对于任意一个点，早晚都会覆盖他，只要确保递推中一定能够覆盖所有点就可以。
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N=20,M=1<<N;
const double eps=1e-6;
int p[N][N];
typedef pair<double,double> PII;
PII q[N];
int dp[M];
int cmp(double a,double b)
{//浮点数比较要自定义比较函数
if(abs(a-b)<eps) return 0;
if(a>b) return 1;
return -1;
}
void solve()
{
memset(dp,0x3f,sizeof dp);
memset(p,0,sizeof p); //因为很多continue,所以p可以有上一个样例的抛物线
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>q[i].x>>q[i].y;
for(int i=0;i<n;i++)
{
p[i][i]=1<<i;
for(int j=0;j<n;j++)
{
//x不能相同
if(!cmp(q[i].x,q[j].x)) continue;
double x1=q[i].x,y1=q[i].y;
double x2=q[j].x,y2=q[j].y;
double a=(y1/x1-y2/x2)/(x1-x2);
if(a>=0) continue;
double b=(y1/x1)-a*x1;
int state=0;
//可能覆盖很多点,枚举一下多少点在线上
for(int k=0;k<n;k++)
{
double x=q[k].x,y=q[k].y;
if(!cmp(a*x*x+b*x,y)) state+=1<<k;
}
p[i][j]=state;
}
}
dp[0]=0;
for(int i=0;i<1<<n;i++)
{
int x=0;
//随便找到一个没有覆盖的点
for(int j=0;j<n;j++)
if((i>>j&1) ==0) {x=j;break;}
//枚举包含x的所有抛物线
for(int j=0;j<n;j++)
dp[i|p[x][j]]=min(dp[i|p[x][j]],dp[i]+1);
}
cout<<dp[(1<<n)-1]<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}