主要和luogu第一篇题解思路一样 第二个优化真的hei牛逼
若令x 为满足 S&(1<<(x−1))=0 的最小正整数，则由S扩展的转移的所有线都要经过 x
先打1 4再打2 2和先打2 3再打 1 4一样
如果这一次转移不打 x ，那以后还要再回过头来打 x 这就是多余的转移。
因为经过 x 的线数量是 nnn ，所以每次转移涉及到的线就从n2 变成了 n
只要预处理一下 0−218的对应的x 就能做到 O(Tn2n)
1 /* 2 id:gww 3 language:C-- 4 5 */ 6 #include<bits/stdc++.h> 7 using namespace std; 8 #define dou double 9 const int N=20,inf=0x3f; 10 const double eps=1e-6;//精度 11 int n,m,pw[N][N],c[1<<N],f[1<<N]; 12 dou x[N],y[N]; 13 inline int rd() 14 { 15 int x=0,w=0;char ch=0; 16 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 17 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 18 return w?-x:x; 19 } 20 21 inline void qab(double &a,double &b,double x1,double y1,double x2,double y2) 22 { 23 a=(x2*y1-x1*y2)/(x1*x2*(x1-x2)); 24 b=(x1*x1*y2-x2*x2*y1)/(x1*x2*(x1-x2)); 25 } 26 27 void pre() 28 { 29 for(int i=1;i<=n;i++) 30 for(int j=1;j<=n;j++) 31 { 32 dou a,b; 33 if(fabs(x[i]-x[j])<eps) continue;//x在同一直线上肯定不能构成抛物线 34 qab(a,b,x[i],y[i],x[j],y[j]); 35 if(a>-eps) continue;//a<0 36 for(int k=1;k<=n;k++)//记录这两个点构成的抛物线能打到的猪的状态 37 if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps) pw[i][j]|=(1<<(k-1)); 38 } 39 } 40 41 void dp() 42 { 43 for(int i=0;i<(1<<n);i++) 44 { 45 int j=c[i]; 46 f[i|(1<<(j-1))]=min(f[i|1<<(j-1)],f[i]+1);//单独转移 47 for(int k=1;k<=n;k++) f[i|pw[j][k]]=min(f[i|pw[j][k]],f[i]+1);//经过j的所有抛物线 48 } 49 } 50 51 int main() 52 { 53 for(int i=0;i<(1<<18);i++)//预处理出i状态时必须经过的最小编号的猪 54 { 55 int j=1; 56 for(;j<=18&&(i&(1<<(j-1)));j++); 57 c[i]=j; 58 } 59 int T=rd(); 60 while(T--) 61 { 62 memset(pw,0,sizeof(pw)); 63 memset(f,inf,sizeof(f));f[0]=0; 64 n=rd(),m=rd();int fi=(1<<n)-1; 65 for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); 66 pre(); 67 dp(); 68 printf("%d ",f[fi]); 69 } 70 return 0; 71 }
暴力