愤怒的小鸟

洛咕

题意:给定\(n(n<=18)\)只小猪的位置,保证在第一象限,从\((0,0)\)处选用最少数量的抛物线打掉所有的小猪.抛物线\(y=ax^2+bx\),其中\(a<0\)且\(a,b\)均为实数.

分析:这种小范围不是搜索就是状压DP,但其实这两种东西在本质上都是穷举,只是看你喜欢写哪种了.对于本题而言,带有几个简单剪枝的搜索秒杀状压DP.

方法一:搜索+简单剪枝:设\(dfs(now,u,v)\)三个状态分别表示当前考虑到了第\(now\)只猪,建立了\(u\)条抛物线,\(now\)只小猪中有\(v\)只是单独还未处理的.

那么对于当前这种小猪,如果它能被之前已经建立的抛物线打掉,当然就直接打掉.否则的话,它要么与前面\(v\)只中的一只新建立一条抛物线,要么自己也加入单独的队伍之中.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int N=1000;
int T,n,m,ans;
double eps=1e-6,xx[N],yy[N];
double x[N],y[N],pwx_x[N],pwx_y[N];
inline void dfs(int now,int u,int v){
    if(u+v>=ans)return;//最优性剪枝
    if(now>n){ans=u+v;return;}
    for(int i=1;i<=u;++i)//如果能被之前的抛物线打掉,直接return
        if(fabs(pwx_x[i]*x[now]*x[now]+pwx_y[i]*x[now]-y[now])<eps){
            dfs(now+1,u,v);return;
        }
    for(int i=1;i<=v;++i){//否则就考虑能否跟前面单独的一只建抛物线
        if(fabs(x[i]-x[now])<eps)continue;
        double A=(double)(xx[i]*y[now]-yy[i]*x[now])/(1.0*xx[i]*x[now]*(x[now]-xx[i]));
        if(A>=0.0)continue;
        double B=(double)(y[now]-A*x[now]*x[now])/(1.0*x[now]);
        pwx_x[u+1]=A;pwx_y[u+1]=B;double xxx=xx[i],yyy=yy[i];
        for(int j=i;j<v;++j)xx[j]=xx[j+1],yy[j]=yy[j+1];
        dfs(now+1,u+1,v-1);
        for(int j=v;j>i;--j)xx[j]=xx[j-1],yy[j]=yy[j-1];
        xx[i]=xxx;yy[i]=yyy;//回溯...
    }
    xx[v+1]=x[now];yy[v+1]=y[now];dfs(now+1,u,v+1);//还可以自己加入单独的队伍
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)scanf("%lf%lf",&x[i],&y[i]);       
        ans=1e9;dfs(1,0,0);printf("%d\n",ans);
    }
    return 0;
}

方法二:状压DP.设\(f[i]\)表示当前打掉小猪的状态为i时的最少抛物线数量(0代表没被打掉,1代表已经打掉了).预处理\(g[i][j]\)表示抛物线过\(i,j\)两只小猪时能打掉的所有小猪的集合.

那么对于一个状态\(i\),就考虑从它第一只没有被打掉的小猪\(j\)转移过来,转移的时候要么是\(j\)单独建立一条抛物线\(f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1)\),要么是找到令一只小猪\(k\),\(f[i|g[j][k]]=min(f[i|g[j][k]],f[i]+1)\).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int N=20;
int T,n,m,g[N][N],f[1<<N];
double eps=1e-6,x[N],y[N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        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)g[i][j]=0;//初始化
        for(int i=1;i<n;++i)//三方预处理g数组
            for(int j=i+1;j<=n;++j){
                if(fabs(x[i]-x[j])<eps)continue;
                double A=(double)(x[j]*y[i]-x[i]*y[j])/(1.0*x[j]*x[i]*(x[i]-x[j]));
                if(A>=0)continue;
                double B=(double)(y[i]-A*x[i]*x[i])/x[i];
                for(int k=1;k<=n;++k){
                    if(fabs(A*x[k]*x[k]+B*x[k]-y[k])<eps)g[i][j]|=1<<(k-1);
                }
            }
        for(int i=0;i<(1<<n);++i)f[i]=1e9;f[0]=0;//初始化
        for(int i=0;i<(1<<n);++i)
            for(int j=1;j<=n;++j){
                if(!(i&(1<<(j-1)))){//找到第一个没打掉的猪j
                    for(int k=j;k<=n;++k){
                        if(j==k)f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1);
                        if(fabs(x[j]-x[k])<eps)continue;
                        f[i|g[j][k]]=min(f[i|g[j][k]],f[i]+1);
                    }
                }
            }
        printf("%d\n",f[(1<<n)-1]);
    }
    return 0;
}

本题还有一个细节就是,对于实数的判等,千万不要直接上\(=\),而是要\(fabs(x,y)<eps\),其中\(eps\)是自己设置的精度,一般\(1e-6\)就好了.

愤怒的小鸟

原文：https://www.cnblogs.com/PPXppx/p/11625615.html