愤怒的小鸟「NOIP2016」

题意

Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说，这款游戏是在一个平面上进行的。

有一架弹弓位于 \((0,0)\) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 \(y=ax^2+bx\) 的曲线，其中 \(a,b\) 是Kiana 指定的参数，且必须满足 \(a < 0\)，\(a,b\) 都是实数。

当小鸟落回地面（即 \(x\) 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 \(n\) 只绿色的小猪，其中第 \(i\) 只小猪所在的坐标为 \(\left(x_i,y_i \right)\)。

如果某只小鸟的飞行轨迹经过了 \(\left( x_i, y_i \right)\)，那么第 \(i\) 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；

如果一只小鸟的飞行轨迹没有经过 \(\left( x_i, y_i \right)\)，那么这只小鸟飞行的全过程就不会对第 \(i\) 只小猪产生任何影响。

例如，若两只小猪分别位于 \((1,3)\) 和 \((3,3)\)，Kiana 可以选择发射一只飞行轨迹为 \(y=-x^2+4x\) 的小鸟，这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有 \(T\) 个关卡，现在 Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。

思路

既然是要给学弟讲那就写长一点吧
————sckldasjdca

首先把题目中一些比较显然的地方指出来：

1. \(m\)是为了方便你打部分分设定的，忽视即可。

2. 这道题\(n\)最大也只有\(18\)，不是状压就是搜索。（虽然有时候毒瘤出题人会把\(O(1)\)题伪装成这样，但是这是\(D2T3\)，所以不太可能）。

3. 没有第\(3\)条。

考虑状压求解本题。

设\(dp[S]\)表示杀害的猪状态为\(S\)的时候最小答案。（\(1\)为杀死，\(0\)为存活）

最坏的情况下我们多加一条线只能多杀一头猪，这种情况转移为\(dp[S|1<<(i-1)]=min(dp[S|1<<(i-1)],dp[S]+1)\)

比较正常的情况是我们这一条线可以杀好几头猪。由算数基本定理，显然两个点可以唯一确定一条线，那么对于每两个点，我们都预处理出穿过它们的抛物线能够穿过的所有点的状态即可。

这种情况转移为\(dp[S|lines[i][j]]=min(dp[S|lines[i][j]],dp[S]+1)\)

不难看出，这样的状压时间复杂度为\(O(n^22^n)\)，对于本题\(n=18\)的极限数据大概要跑\(1e8\)，非松人士不太可能过。

考虑优化朴素的状压。

假设\(x\)是一个当前还没有被杀死的猪中编号最小的那一个，即\(x\)为满足\(S\&(1<<(x-1))=0\)的最小正整数，那么先转移\(x\)必然不劣于其他任何转移。

正确性不难说明：现在不杀，早晚得杀。与其让它活着受苦，不如就此终结它的猪生。

所以每一次不管如何都要干掉这个\(x\)，那么转移的复杂度就少了一个\(n\)。

与处理一下每个状态对应的\(x\)值，就可以将状压的时间复杂度优化到\(O(n2^n)\)，由于本题时限有\(2s\)所以可以过。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {
    
    const int N=20;
    const double eps=1e-8;

    int t,n,m;
    int lowunbit[1<<N],lines[N][N],dp[1<<N];
    double x[N],y[N];

    inline void solve_eqa (double &x,double &y,double a1,double b1,double c1,double a2,double b2,double c2) {
        y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
        x=(c1-b1*y)/a1;
    }
    inline void init_low () {
        for (register int i=0,j; i<(1<<18); ++i) {
            j=1;
            for (; j<=18&&(i&(1<<(j-1))); ++j);
            lowunbit[i]=j;
        }
    }
    inline void clear_var () {
        memset(lines,0,sizeof(lines));
        memset(dp,127,sizeof(dp));
        dp[0]=0;
    }
    inline void work_lines () {
        for (register int i=1; i<=n; ++i) {
            for (register int j=1; j<=n; ++j) {
                if (fabs(x[i]-x[j])<eps) continue;
                double a,b;
                solve_eqa(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);
                if (a>-eps) continue;
                for (register int k=1; k<=n; ++k) {
                    if (fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps) lines[i][j]|=(1<<(k-1));
                }
            }
        }
    }
    inline void work_dp () {
        for (register int i=0,j; i<(1<<n); ++i) {
            j=lowunbit[i];
            dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);
            for (register int k=1; k<=n; ++k) {
                dp[i|lines[j][k]]=min(dp[i|lines[j][k]],dp[i]+1);
            }
        }
    }

    inline void MAIN () {
        init_low();
        read(t);
        while (t--) {
            clear_var();
            read(n),read(m);
            for (register int i=1; i<=n; ++i) {
                scanf("%lf%lf",&x[i],&y[i]);
            }
            work_lines();
            work_dp();
            write(dp[(1<<n)-1]),putchar('\n');
        }
    }
    
}

int main () {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    Project::MAIN();
}

愤怒的小鸟「NOIP2016」

原文：https://www.cnblogs.com/ilverene/p/11823807.html