zcmimi's blog

查看原题

点击跳转

f[sta]为死了的猪状态为sta时最少需要多少鸟

f[sta|line(i,j)]=\min(f[sta]+1)(line(i,j)表示经过i,j的抛物线能杀死的🐖的集合)

f[sta|(1<<i)]=\min(f[sta]+1)

优化:

若令x为满足sta\&(1<<(x-1))=0的最小正整数,则由sta扩展的转移的所有线都要经过x

#include<bits/stdc++.h>
const int N=20;
typedef double db;
const db eps=1e-8;
void eq(db&a,db&b,db x,db y,db z,db X,db Y,db Z){ // ax+by=z,aX+bY=Z
    b=(x*Z-X*z)/(x*Y-X*y);
    a=(z-y*b)/x;
}
db x[N],y[N];
int n,m,f[1<<N],lb[1<<N],l[N][N];
void cmin(int&x,int y){if(y<x)x=y;}
void solve(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",x+i,y+i);
    memset(l,0,sizeof l);
    for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j){
        if(fabs(x[i]-x[j])<eps)continue;
        db a,b;eq(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(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps)l[i][j]|=1<<k-1;
    }
    memset(f,126,sizeof f);
    f[0]=0;
    int lim=1<<n;
    for(int s=0,x;s<lim;++s){
        x=lb[s];
        cmin(f[s|(1<<x-1)],f[s]+1);
        for(int k=1;k<=n;++k)
            cmin(f[s|l[x][k]],f[s]+1);
    }
    printf("%d\n",f[(1<<n)-1]);
}
int main(){
    for(int i=0,j;i<1<<18;++i){
        for(j=1;j<=18&&i&(1<<j-1);++j);
        lb[i]=j;
    }
    int T;scanf("%d",&T);
    while(T--)solve();
}
LG 2831 愤怒的小鸟
comment评论
Search
search