愤怒的小鸟

愤怒的小鸟（状压dp）

弹弓在(0, 0)处，有一堆猪在第一象限，问你用鸟打几次能把猪全部打掉。鸟的飞行路线是处在第一象限的抛物线。猪的个数n<=18。

这道题一看就是状压dp啊。。枚举2^n的状态，对于一个状态，它最前面的那个零，也就是最前面的还没打掉的猪，肯定是要被解决的。所以你就枚举另一个猪，确定抛物线，看看哪些猪被打到，然后转移状态就行了。时间复杂度(O(n2^n))。

#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxn=18, INF=1e9; const double eps=1e-8;
int n, m, t, mi[maxn];
double pigx[maxn], pigy[maxn];
int link[maxn][maxn], f[1<<maxn];

inline double abs(double x){ return x<0?-x:x; }

void init_mi(){
    mi[0]=1;
    for (int i=1; i<maxn; ++i) mi[i]=mi[i-1]<<1;
}

int firzero(int x){
    for (int i=n-1; i>=0; --i)
        if ((x&mi[i])==0) return n-i-1;
    return -1;
}

int main(){
    init_mi();
    scanf("%d", &t);
    double a, b, bs, c1, c2, c3, c4;
    int pos, tmp;
    for (int tt=0; tt<t; ++tt){
        memset(link, 0, sizeof(link));
        scanf("%d%d", &n, &m);
        for (int i=0; i<n; ++i)
            scanf("%lf%lf", &pigx[i], &pigy[i]);
        for (int i=0; i<n; ++i)
            for (int j=0; j<n; ++j){
                if (i==j){
                    link[i][j]=mi[n-i-1];
                    continue;
                }
                bs=pigx[j]/pigx[i];
                c1=pigx[i]*pigx[i]*bs; c2=pigy[i]*bs;
                c3=pigx[j]*pigx[j]; c4=pigy[j];
                a=(c4-c2)/(c3-c1); b=(c4-a*c3)/pigx[j];
                if (a>=0) continue;
                for (int k=0; k<n; ++k){
                    if (abs(a*pigx[k]*pigx[k]+b*pigx[k]-pigy[k])<eps)
                        link[i][j]+=mi[n-k-1];
                }
            }
        std::fill(f, f+(1<<maxn), INF); f[0]=0;
        for (int i=0; i<(1<<n)-1; ++i){
            pos=firzero(i);
            for (int j=0; j<n; ++j){
                tmp=i|link[pos][j];
                f[tmp]=std::min(f[tmp], f[i]+1);
            }
        }
        printf("%d
", f[(1<<n)-1]);
    }
    return 0;
}