设f[s]表示二进制集合表示下的s集合都打掉用了多少小鸟。
预处理出lne[i][j]表示i、j确定的抛物线能打掉的小鸟集合。
于是就有f[s|lne[i][j]]=min(f[s|lne[i][j]],f[s]+1);
什么？两个点确定不了抛物线？原点是不是被忘掉了……
代码如下
#include<cstdio> #include<cctype> #include<cmath> #include<iostream> #include<cstring> using namespace std; double x[1000],y[1000]; int lne[1000][1000]; int f[800000]; int main(){ int T; cin>>T; while(T--){ int n,m; cin>>n>>m; memset(lne,0,sizeof(lne)); memset(f,127,sizeof(f)); for(int i=1;i<=n;++i) cin>>x[i]>>y[i]; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j){ if(i==j) continue; double d=y[j]-(y[i]/x[i]*x[j]),c=x[j]*(x[j]-x[i]); double a=d/c,b=(y[i]-x[i]*x[i]*a)/x[i]; if(a<0) for(int k=1;k<=n;++k) if(abs(x[k]*x[k]*a+x[k]*b-y[k])<=1e-7) lne[i][j]|=(1<<(k-1)); } int Max=(1<<n)-1; for(int i=1;i<=n;++i) f[1<<(i-1)]=1; f[0]=0; for(int i=0;i<=Max;++i){ int pos=1; while(i>>(pos-1)&1) ++pos; if(f[i|(1<<(pos-1))]>f[i]+1) f[i|(1<<(pos-1))]=f[i]+1; for(int j=pos+1;j<=n;++j) f[i|lne[pos][j]]=min(f[i|lne[pos][j]],f[i]+1); } printf("%d ",f[Max]); } return 0; }