P2831 愤怒的小鸟（状压dp）

P2831 愤怒的小鸟

我们先预处理出每个猪两两之间（设为$u,v$）和原点三点确定的抛物线（当两只猪横坐标相等时显然无解）

处理出$u,v$确定的抛物线一共可以经过多少点，记为$lines[u][v]$

设$f[i]$表示已经被消灭的猪的集合为二进制表示为$i$时，需要的最小抛物线数

显然$f[0]=0$

$f[i|(1<<(u-1))]=min(f[i|(1<<(u-1)],f[i]+1)$（一条抛物线只串一个点）

$f[i|lines[u][v]]=min(f[i|lines[u][v]],f[i]+1)$

然鹅这是$O(Tn^{2}2^{n})$，ccf的老爷机会T

那么我们考虑优化

我们发现加上抛物线时，先串$1,4$与先串$2,3$没有区别，但是我们两种都用不同的顺序枚举了一遍。

那么我们可以处理出集合$i$的$mex$（在集合中没有出现的最小正整数）

枚举时加上限制条件：一定要包含$mex[i]$

于是枚举就从$O(n^{2})$降到了$O(n)$

总复杂度就降到了$O(Tn2^{n})$

end.

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define re register

using namespace std;

typedef double db;

int min(int &a,int &b){return a<b?a:b;}

#define N 524589

const db eps=1e-;

db x[],y[];

int t,n,m,lines[][],f[N],mex[N];

void calc(db &a,db &b,db x1,db y1,db x2,db y2){

    b=(x1*x1*y2-x2*x2*y1)/(x1*x1*x2-x1*x2*x2);

    a=(y1-x1*b)/(x1*x1);

}//用于解一元二次方程组

int main(){

    for(re int i=,j;i<;++i){//预处理mex

        for(j=;(i&(<<j))&&j<;++j);

        mex[i]=j;

    }scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m); db a,b;

        for(re int i=;i<=n;++i)

            scanf("%lf%lf",&x[i],&y[i]);

        for(re int i=;i<=n;++i)

            for(re int j=;j<=n;++j){

                lines[i][j]=;

                if(fabs(x[i]-x[j])<eps) continue;//横坐标相等无解

                calc(a,b,x[i],y[i],x[j],y[j]);

                if(a>-eps) continue;

                for(re int u=;u<=n;++u)

                    if(fabs(a*x[u]*x[u]+b*x[u]-y[u])<eps)

                        lines[i][j]|=(<<(u-));//找到这条抛物线能连到的所有点

            }

        memset(f,,sizeof(f)); f[]=;

        for(re int i=,j=mex[i];i<(<<n);j=mex[++i]){

            f[i|(<<j)]=min(f[i|(<<j)],f[i]+); //单个点用掉一条的情况

            for(re int u=;u<=n;++u)//枚举的抛物线必须穿过j

                f[i|lines[j+][u]]=min(f[i|lines[j+][u]],f[i]+);

        }

        printf("%d\n",f[(<<n)-]);

    }return ;

}