Link
Solve
我们注意到(n≤18)所以考虑状压$DP或者暴力。
定义(F[S])表示(S)为(1)位置上的猪已经被打掉的最少次数
显然我们能很容易的得到转移方程
(dp[0]=0)
(dp[S|line[i][j]]=min(dp[S]+1))
(dp[S|(1<<(i-1)]=min(dp[S]+1))
考虑如何优化
因为我们先打(1,4)再打(2,3)的代价和先打(2,3)再打(1,4)的代价是一样的。
所以我们找一个(x)使得(S&(1<<x-1)==0),使得转移到(S)这个状态必须要先打(x)这个点,就是把最低的(0)位置变成(1),因为经过(x)的线的条数是(O(n))所以总的时间复杂度是(O(nast 2^n))
这种优化方法对于取的顺序不影响答案是可以学习的
Code
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
int T,N,M,bit[(1<<20)+5],line[20][20],F[(1<<20)+5];
double x[20],y[20];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
void equation(double &x,double &y,double a1,double b1,double c1,double a2,double b2,double c2){ //解方程
y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
x=(c1-b1*y)/a1;
}
void make_bit(){
for(int i=0;i<(1<<18);i++){
int j=1;
for(;j<=18&&i&(1<<j-1);j++);
bit[i]=j;
}
}
int main(){
freopen("terrorist.in","r",stdin);
freopen("terrorist.out","w",stdout);
T=read();
make_bit();
while(T--){
memset(line,0,sizeof line);
memset(F,63,sizeof F);
N=read();M=read();
F[0]=0;
for(int i=1;i<=N;i++)scanf("%lf%lf",&x[i],&y[i]);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++){
if(abs(x[i]-x[j])<eps)continue;
double a,b;
equation(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);
if(a>-eps)continue;
for(int k=1;k<=N;k++)
if(abs(a*x[k]*x[k]+b*x[k]-y[k])<eps)
line[i][j]|=(1<<k-1);
}
for(int i=0;i<(1<<N);i++){
int j=bit[i];
F[i|(1<<j-1)]=min(F[i|(1<<j-1)],F[i]+1);
for(int k=1;k<=N;k++)F[i|line[j][k]]=min(F[i|line[j][k]],F[i]+1);
}
printf("%d
",F[(1<<N)-1]);
}
return 0;
}