【NOIP】提高组2016 愤怒的小鸟

【题意】Universal Online Judge

【算法】状态压缩型DP

【题解】看数据范围大概能猜到是状压了。

根据三点确定一条抛物线，枚举两个点之间的抛物线，再枚举有多少点在抛物线上（压缩为状态c[]），这样预处理出至多n*n/2+n条抛物线。（注意加上只经过一点的抛物线）

然后f[i]表示猪的消灭状态为i的最小步数，转移方程：f[i&c[j]]=min(f[i&c[j]],f[i]+1)。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cctype>

#include<cmath>

using namespace std;

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int maxN=,maxn=;

const double eps=1e-;

int c[maxn],f[maxN],n,tot,qaq;

double x[],y[],a[maxn],b[maxn];

int main(){

    int T=read();

    while(T--){

        n=read();qaq=read();tot=;

        for(int i=;i<n;i++)scanf("%lf%lf",&x[i],&y[i]);

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

            c[++tot]=<<i;

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

                b[++tot]=(y[j]-y[i]*x[j]*x[j]/(x[i]*x[i]))/(x[j]-x[j]*x[j]/x[i]);

                a[tot]=(y[i]-b[tot]*x[i])/(x[i]*x[i]);

                if(a[tot]+eps>){tot--;continue;}

                c[tot]=(<<i)|(<<j);

                for(int k=j+;k<n;k++)if(fabs(a[tot]*x[k]*x[k]+b[tot]*x[k]-y[k])<eps){

                    c[tot]|=(<<k);

                }

            }

        }

        memset(f,0x3f,sizeof(f));

        f[]=;

        for(int i=;i<=tot;i++){

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

                f[j|c[i]]=min(f[j|c[i]],f[j]+);//wei yun suan

            }

        }

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

    }

    return ;

}