马上期末考试了，来一道抛物线复习一下数学知识吧。这样想着，小h打开电脑，找到了这一道题目。
看完题，疑惑：函数axx+bx为什么a必须小于零？想了一下才明白：愤怒的小鸟中，鸟的飞行轨迹开口
朝下，只有a<0，才会开口朝下，不然就会越飞越高。抛物线经过原点，意味着c一定为零，因此2个点
可以确定一条抛物线。那就先把所有抛物线找出来吧，反正n<=18。另外，题目中的m是没用的，纯粹
用来迷惑你。怎么求抛物线呢？对于所有一对点(x1,y1)、(x2,y2)，先构造二元一次方程组：
设a1=x1*x1, b1=x1, c1=y1, a2=x2*x2, b2=x2, c2=y2。则方程组为：x*a1+y*b1=c1, x*a2+y*b2=c2。
解方程：经过推演,易知：y=(c2*a1-c1*a2)/(a1*b2-a2*b1)
x=(c1-b1*y)/a1
代码void jfc(LL &x,LL &y,LL a1,LL b1,LL c1,LL a2,LL b2,LL c2){ y=(c2*a1-c1*a2)/(a1*b2-a2*b1);
然后求抛物线经过哪些点，记录在zt数组中。zt（i，j）代表经过猪i和猪j的抛物线可以杀死的猪。这里用到了状态压缩，zt（i，j）中，二进制下第k位为1代表该抛物线可以杀死猪k。
接下来设计状态。dp i表示猪的生死状态为i时，最少要几个抛物线。然后增加抛物线zt（i，j），dp（i bitor zt（i，j）））=min（dp i）
也有可能单独杀一只，注意特判。
注意浮点数0的判断。还有找抛物线时，如果两个点的横坐标相同，肯定不会在同一抛物线。
代码#include<bits/stdc++.h> defineLL double using namespace std; bool is0(LL x){ return fabs(x)<1e-8; } void jfc(LL &x,LL &y,LL a1,LL b1,LL c1,LL a2,LL b2,LL c2){ y=(c2*a1-c1*a2)/(a1*b2-a2*b1); x=(c1-b1*y)/a1; } int qwq,n,m,dp[1<<20],zt[66][66]; LL x[66],y[66]; int main(){ int i,j,k; scanf("%d",&qwq); while(qwq--){ memset(dp,63,sizeof(dp)); memset(zt,0,sizeof(zt)); dp[0]=0; scanf("%d%d",&n,&m); m=(1<<n)-1; LL a,b; for(i=1;i<=n;i++) scanf("%lf%lf",x+i,y+i); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(!is0(x[i]-x[j])){ jfc(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]); if(a<-1e-8) for(k=1;k<=n;k++) if(is0(a*x[k]*x[k]+b*x[k]-y[k])) zt[i][j]|=1<<(k-1); } for(i=0;i<=m;i++){ for(j=0;j<n;j++) dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+1); for(j=1;j<=n;j++) for(k=1;k<=n;k++) dp[i|zt[j][k]]=min(dp[i|zt[j][k]],dp[i]+1); } cout<<dp[m]<<endl; } return 0; }
超时了3个
时间复杂度：T(n**2)(2**n)
发现转移时有重复转移，考虑把j优化了。是不是所有i扩展的线段都经过编号最小的活猪？
我们预处理出每个i对应的最小活猪编号lowbit i，j=lowbit i，这样就消掉了一重for循环。
证明已死的猪集i，抛物线a、b，b经过活猪k，a经过j。假设b经过j、k，那么也会被扩展到；否则，即使先扩展b，将来也要扩展a，不如先扩展a，避免顺序不同却等效的扩展。
正解#include<bits/stdc++.h> defineLL double using namespace std; bool is0(LL x){ return fabs(x)<1e-8; } void jfc(LL &x,LL &y,LL a1,LL b1,LL c1,LL a2,LL b2,LL c2){ y=(c2*a1-c1*a2)/(a1*b2-a2*b1); x=(c1-b1*y)/a1; } int qwq,n,m,dp[1<<20],zt[66][66],lowbit[1<<20]; LL x[66],y[66]; int main(){ int i,j,k; for(i=0;i<(1<<18);i++){ for(j=0;j<18 && ((1<<j)&i);j++); lowbit[i]=j; } scanf("%d",&qwq); while(qwq--){ memset(dp,63,sizeof(dp)); memset(zt,0,sizeof(zt)); dp[0]=0; scanf("%d%d",&n,&m); m=(1<<n)-1; LL a,b; for(i=1;i<=n;i++) scanf("%lf%lf",x+i,y+i); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(!is0(x[i]-x[j])){ jfc(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]); if(a<-1e-8) for(k=1;k<=n;k++) if(is0(a*x[k]*x[k]+b*x[k]-y[k])) zt[i-1][j]|=1<<(k-1); } for(i=0;i<=m;i++){ j=lowbit[i]; dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+1); for(k=1;k<=n;k++) dp[i|zt[j][k]]=min(dp[i|zt[j][k]],dp[i]+1); } cout<<dp[m]<<endl; } return 0; }
小h注：<是小于号，>是大于号，这两个打不出来。可以自行用dev-cpp 的ctrl&F修改正确
小hctrlF替换文件内容，选项都不选
京公网安备11010502036362号