传送门
状压一眼题。
直接f[i]f[i]f[i]表示未选择状态为iii时的最小次数。
然后考虑现在怎么转移。
显然可以直接枚举消掉某一个点或者某两个点，复杂度O(n22n)O(n^22^n)O(n22n)
由于这个集合里面的所有点最终都会被消掉，因此顺序并不重要。
于是可以强制这一步会消掉lowbit(i)lowbit(i)lowbit(i)
那么当前有两个选择：
- 只消掉lowbit(i)lowbit(i)lowbit(i)
- 还会消掉其它的。
第一种直接递归，第二种可以预处理数组f[i][j]f[i][j]f[i][j]表示如果构造一条过了i,ji,ji,j的抛物线并消去上面的点，剩下的点的集合。
然后转移就很轻松了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int T,TT,n,stat[N][N],f[1<<18],bit[19],mp[(1<<18)+1];
bool g[N][N];
struct Node{double x,y;}p[N];
inline bool check(int pos,double a,double b){return fabs(a*p[pos].x*p[pos].x+b*p[pos].x-p[pos].y)>1e-10;}
inline int lowbit(int x){return x&-x;}
inline int countbit(int x){int ret=0;while(x)x-=lowbit(x),++ret;return ret;}
inline int dfs(int sta){
if(~f[sta])return f[sta];
if(!sta)return f[sta]=0;
if(sta==lowbit(sta))return f[sta]=1;
f[sta]=countbit(sta);
int i=lowbit(sta),staa=sta-lowbit(sta);
f[sta]=min(f[sta],1+dfs(sta^i));
while(staa){
int j=lowbit(staa);
if(!g[mp[i]+1][mp[j]+1])f[sta]=min(f[sta],1+dfs(sta&stat[mp[i]+1][mp[j]+1]));
staa-=j;
}
return f[sta];
}
int main(){
scanf("%d",&T),bit[0]=1,mp[1]=0;
for(int i=1;i<=18;++i)bit[i]=bit[i-1]<<1,mp[bit[i]]=i;
while(T--){
memset(f,-1,sizeof(f)),memset(g,0,sizeof(g)),scanf("%d",&n),scanf("%d",&TT);
for(int i=1;i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(i==j){g[i][j]=1;continue;}
int sta=0;
double a1=p[i].x*p[i].x,b1=p[i].x,c1=-p[i].y,a2=p[j].x*p[j].x,b2=p[j].x,c2=-p[j].y;
double a,b;
if(fabs(b1-b2*a1/a2)>1e-5)b=-(c1-c2*a1/a2)/(b1-b2*a1/a2),a=(-c1-b1*b)/a1;
else{g[i][j]=1;continue;}
if(a>-1e-5){g[i][j]=1;continue;}
else for(int k=1;k<=n;++k)if(check(k,a,b))sta|=1<<(k-1);
stat[i][j]=sta;
}
printf("%d\n",dfs((1<<n)-1));
}
return 0;
}