时隔n久，又回到了这道题。我还记得普及组时一头雾水的样子
题外话不扯，这道题是一道比较好的dp题
一眼就能看出来这是状态压缩。
状态压缩dp最大的特点是什么呢？（暴力）
我们需要暴力的枚举各种决策，然后转移
枚举决策是个很重要的思想。也是经常考察的知识点
所以需要多加练习
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using std::min;
double x[30],y[30];
int chance[301000],tot;
double eps=0.00000001;
int f[1<<(19)];
void calc(double &A,double &B,int i,int j)
{
double a=y[i],b=x[i]*x[i],c=x[i];
double d=y[j],e=x[j]*x[j],f=x[j];
A=(a*f-c*d)/(b*f-c*e);
B=(a*e-d*b)/(c*e-f*b);
return ;
}
double abs(double a)
{
if(a<0) return a*-1.0;
return a;
}
bool get(double a,double b,int k)
{
double c=a*x[k]*x[k]+b*x[k];
if(abs(y[k]-c)<=eps)
return true;
return false;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
tot=0;
scanf("%d%d",&n,&m);//m好像在暴力面前并没有什么乱用
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(int i=1;i<=n;i++)
{
chance[++tot]=1<<(i-1);
for(int j=i+1,vis=0;j<=n;j++)
{
double a,b;
calc(a,b,i,j);//计算函数
if(a>=0||vis&(1<<(j-1))) continue;//符合现实，vis是用来去重，防止一次打掉多个的决策被重复枚举
int pas=0;
for(int k=1;k<=n;k++)
if(get(a,b,k)) //同时被打下
{
pas|=1<<(k-1);
vis|=1<<(k-1);
}
chance[++tot]=pas;
}
}
memset(f,127,sizeof(f));
f[0]=0;
for(int i=0;i<(1<<n);i++)
for(int j=1;j<=tot;j++)
f[i|chance[j]]=min(f[i|chance[j]],f[i]+1);//转移
printf("%d
",f[(1<<n)-1]);
}
}