题意：给定一些点，求用多少条抛物线能覆盖这些点。
(1leq nleq 18,0 < x_i,y_i < 10)
思路
由于给定的(n)很少，可以考虑(2^n)或(n)的高次幂级别的算法。因此考虑状压。
考虑将点是否被覆盖作为状态，设其为(f_i)，枚举每条抛物线可以覆盖哪些点，设为(g_j)，然后尝试优化(f_{i or g_j})。
那么现在来考虑抛物线，注意到(x)已知，则事实上，我们需要求解二元一次方程。我们选择任意两个点，然后解形如
(egin{cases} ax_1^2+bx_1=y_1\ ax_2^2+bx_2=y_2end{cases})
的方程，其中(x,y)是已知值，(a,b)为要求的值。（这个应该都会解吧）
由于抛物线上可能还有其他点，所以还要枚举其他点是否在抛物线上。并且由于(x_i)，(y_i)为小数(浮点数)，计算出来的(a)，(b)亦为小数(浮点数)，浮点数的运算会有偏差，所以要注意浮点数的比较：判断两个数的差是否超过精度限制，若未超过，即可判定相等。
上代码
#include<bits/stdc++.h>
using namespace std;
double x[20],y[20],a,b;
int n,m,t,gp,g[325],f[264817];
void solve(int i,int j)
{
double a1=x[i]*x[i],b1=x[i];
double a2=x[j]*x[j],b2=x[j];
a=(y[j]*(b1/b2)-y[i])/(a2*(b1/b2)-a1);
b=(y[i]-a*a1)/x[i];
}//解方程
int find()
{
int ans=0;
for (int i=1;i<=n;i++)
{
if (abs(x[i]*x[i]*a+x[i]*b-y[i])<=1e-10)
{
ans|=1<<(i-1);
}
}
return ans;
}
int main()
{
cin>>t;
for (int tt=1;tt<=t;tt++)
{
cin>>n>>m;
gp=0;
for (int i=0;i<(1<<(n));i++)
f[i]=2147483647;
for (int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
}
for (int i=1;i<=n;i++)
{
g[++gp]=1<<(i-1);
for (int j=i+1;j<=n;j++)
{
solve(i,j);
if (a>=0) continue;
g[++gp]=find();
}
}//预处理
f[0]=0;
for (int i=0;i<(1<<(n));i++)
{
if (f[i]==2147483647) continue;
for (int j=1;j<=gp;j++)
{
{
f[i|g[j]]=min(f[i|g[j]],f[i]+1);
}
}
}
cout<<f[(1<<(n))-1]<<endl;
}
return 0;
}
这份代码在(luogu)上的结果是(3.48S / 1.61MB)（(luogu)的空间算法与(NOIP)的并不相同，请注意）
其实我们还能尝试优化，注意到选择抛物线的顺序并不影响答案，因此，我们可以固定一个枚举的顺序，在这里，我们将顺序定为选择能覆盖最前面的没被覆盖的点的抛物线。这样就可以省掉一些不必要的枚举，取得质的飞跃。
实现优化，我们只需将原来(dp)的循环改为：
for (int i=0;i<(1<<(n));i++)
{
if (f[i]==2147483647) continue;
int ti=i,tn=1;
while (ti&1)
{
ti>>=1;
tn++;
}
for (int j=1;j<=gp;j++)
{
if ((g[j]>>(tn-1))&1)
{
f[i|g[j]]=min(f[i|g[j]],f[i]+1);
}
}
}
优化后，程序跑出了(144ms/1.65MB)（(luogu)的空间算法与(NOIP)的并不相同，请注意）