uoj265【2016提高】愤怒的小鸟（状压dp）

54 阅读 0 评论 36 点赞

我是靠谱客的博主要减肥月饼，最近开发中收集的这篇文章主要介绍uoj265【2016提高】愤怒的小鸟（状压dp），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

首先每两个点可以确定一条抛物线，一条抛物线可能打掉很多猪。所以我们先 $O(n^2)$ 预处理一下第i个点和第j个点所确定的抛物线（算个公式就好了），如果a<0才合法，（注意精度问题，还有特判横坐标相等的，小心除0）然后对于这条抛物线，如果合法的话，我们 $O(n)$ 扫一遍，看有没有其他的点也在这条抛物线上。用b数组记录一下（n<=18,我们显然可以用二进制压缩状态，共 $2^n$ 种，把这条抛物线会打死的猪标为1，其他猪为0）。进行dp，我们对于每个状态st，找到第一头还活着的猪，记为i，反正i迟早得死，我们让它这一次死。枚举能打死他的抛物线，一波带走抛物线上所有点，接着dp。复杂度 $2^n·n$
递归版更快，递推版更短小。

递归版

#include <bits/stdc++.h>
#define N 20
#define eps 1e-10
#define inf 0x3f3f3f3f
int tst,n,m,f[1<<20],b[N][N],ans=20;
inline int min(int x,int y){return x<y?x:y;}
inline double abs(double x){return x<0?-x:x;}
struct node{
    double x,y;
}a[N];
/*枚举s的子集（没有空集）
    for(int s1=s;s1>=1;s1=s&(s1-1){}*/ 
int dp(int st){
    if(f[st]!=inf) return f[st];
    if(st==0) return 0;//注意特判，不然会死。 
    int tot=0;
    for(int j=0;j<n;++j) if(st&(1<<j)) ++tot;
    int i=0;while(!(st&(1<<i))) ++i;
    if(tot==2){
        int j=i+1;while(!(st&(1<<j))) ++j;//注意！优先级高于一切。。。 
        if(b[i][j]) return 1;
        else return 2;
    }
    if(tot==1) return 1;
    for(int j=i;j<n;++j)
        if(b[i][j]) f[st]=min(f[st],dp(st&((1<<n)-1-b[i][j]))+1);
    return f[st];
}
int main(){
//  freopen("testdata.in","r",stdin);
    scanf("%d",&tst);
    while(tst--){
        scanf("%d%d",&n,&m);memset(b,0,sizeof(b));
        memset(f,0x3f,sizeof(f));
        for(int i=0;i<n;++i) b[i][i]=1<<i;
        for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j){
                double aa=0,bb=0;
                if(abs(a[i].x-a[j].x)<eps) continue;
                aa=(a[i].y*a[j].x-a[i].x*a[j].y)/(a[i].x*a[j].x*(a[i].x-a[j].x));
                bb=a[i].y/a[i].x-aa*a[i].x;
                if(aa>-eps) continue;//注意精度eps相当于0 
                b[i][j]=(1<<i)+(1<<j);
                for(int k=j+1;k<n;++k)
                    if(abs(a[k].x*a[k].x*aa+a[k].x*bb-a[k].y)<eps) b[i][j]+=(1<<k);
            }
        int ans=dp((1<<n)-1);
        printf("%dn",ans);
    }
    return 0;
}

递推版

#include <bits/stdc++.h>
#define N 20
#define eps 1e-10
#define inf 0x3f3f3f3f
int tst,n,m,f[1<<20],b[N][N],bin[N];//b的1表示打出这条抛物线后还活着的猪 
inline int min(int x,int y){return x<y?x:y;}
inline double abs(double x){return x<0?-x:x;}
struct node{
    double x,y;
}a[N];
int main(){
//  freopen("testdata.in","r",stdin);
    scanf("%d",&tst);
    bin[0]=1;for(int i=1;i<=18;++i) bin[i]=bin[i-1]<<1;
    while(tst--){
        scanf("%d%d",&n,&m);memset(b,0,sizeof(b));
        for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j){
                double x1=a[i].x,x2=a[j].x,y1=a[i].y,y2=a[j].y;
                double A=0,B=0;b[i][j]=bin[n]-1;
                if(abs(x1-x2)<eps) continue;
                A=(y1*x2-x1*y2)/(x1*x2*(x1-x2));
                B=y1/x1-A*x1;
                if(A>-eps) continue; 
                for(int k=0;k<n;++k)
                    if(abs(a[k].x*a[k].x*A+a[k].x*B-a[k].y)<eps) b[i][j]-=bin[k];
            }
        f[0]=0;
        for(int i=1;i<=bin[n]-1;++i){
            int x=0;for(;;x++) if(i&bin[x]) break;
            f[i]=f[i-bin[x]]+1;//只打掉这头猪 
            for(int j=x+1;j<n;++j) f[i]=min(f[i],f[i&b[x][j]]+1);
        }
        printf("%dn",f[bin[n]-1]);
    }
    return 0;
}