洛谷P2831 [Noip2016]愤怒的小鸟

题目描述

• Kiana最近沉迷于一款神奇的游戏无法自拔。
• 简单来说，这款游戏是在一个平面上进行的。
• 有一架弹弓位于(0,0)处，每次Kiana可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如y=ax2+bx的曲线，其中a,b是Kiana指定的参数，且必须满足a<0。
• 当小鸟落回地面(即x轴）时，它就会瞬间消失。
• 在游戏的某个关卡里，平面的第一象限中有n只绿色的小猪，其中第i只小猪所在的坐标为(xi,yi)。
• 如果某只小鸟的飞行轨迹经过了(xi,yi),那么第i只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；
• 如果一只小鸟的飞行轨迹没有经过(xi,yi)，那么这只小鸟飞行的全过程就不会对第i只小猪产生任何影响。
• 例如，若两只小猪分别位于(1,3)和(3,3)，Kiana可以选择发射一只飞行轨迹为y=−x2+4x的小鸟，这样两只小猪就会被这只小鸟一起消灭。
• 而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
• 这款神奇游戏的每个关卡对Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在输入格式中详述。
• 假设这款游戏一共有T个关卡，现在Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。

输入输出格式

输入格式

• 第一行包含一个正整数T，表示游戏的关卡总数。
• 下面依次输入这T个关卡的信息。每个关卡第一行包含两个非负整数n,m，分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。接下来的n行中，第i行包含两个正实数(xi,yi)，表示第i只小猪坐标为(xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。
• 如果m=0，表示Kiana输入了一个没有任何作用的指令。
• 如果m=1，则这个关卡将会满足：至多用⌈n3+1⌉只小鸟即可消灭所有小猪。
• 如果m=2，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少⌊n3⌋只小猪。
• 保证1≤n≤18，0≤m≤2，0<xi,yi<10，输入中的实数均保留到小数点后两位。
• 上文中，符号⌈c⌉⌊c⌋分别表示对c向上取整和向下取整

输出格式

• 对每个关卡依次输出一行答案。
• 输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量

输入输出样例

输入样例#1

• 2
  2 0
  1.00 3.00
  3.00 3.00
  5 2
  1.00 5.00
  2.00 8.00
  3.00 9.00
  4.00 8.00
  5.00 5.00

输出样例#1

• 1
  1

输入样例#2

• 3
  2 0
  1.41 2.00
  1.73 3.00
  3 0
  1.11 1.41
  2.34 1.79
  2.98 1.49
  5 0
  2.72 2.72
  2.72 3.14
  3.14 2.72
  3.14 3.14
  5.00 5.00

输出样例#2

• 2
  2
  3

输入样例#3

• 1
  10 0
  7.16 6.28
  2.02 0.38
  8.33 7.78
  7.68 2.09
  7.46 7.86
  5.77 7.44
  8.24 6.72
  4.42 5.11
  5.42 7.79
  8.15 4.99

输出样例#3

• 6

说明

样例解释1

• 这组数据中一共有两个关卡。
• 第一个关卡与问题描述中的情形相同，2只小猪分别位于(1.00,3.00)和 (3.00,3.00)，只需发射一只飞行轨迹为y=−x2+4x的小鸟即可消灭它们。
• 第二个关卡中有5只小猪，但经过观察我们可以发现它们的坐标都在抛物线 y=−x2+6x上，故Kiana只需要发射一只小鸟即可消灭所有小猪。

数据范围

原题地址

洛谷P2831 UOJ#265

分析 状态压缩 + 记忆化搜索 + 剪枝

• 很容易想到暴搜枚举两个未被消灭的点来确定一条抛物线，并判断这条抛物线能消灭多少个点，消灭完所有点即为一种方案（当然，也可以每次直接选择消灭某一个点）
• 这样裸搜肯定会超时，我们考虑如何优化：
  
  1. 当我们枚举确定抛物线的第一个点的时候，记录当前枚举到的点i，则下一次只要从点i+1开始枚举即可
  2. 最多只有18个点，可以将其压缩成一个18位的二进制数，若第i位为1表示第i个点已被消灭，那么枚举点的时候直接用当前二进制状态判断是否可选即可
  3. 我们记f[s]表示二进制状态为s的当前最优解，如果发现目前已发射的小鸟数G≥f[s]，则继续搜下去肯定时不优的，否则就令f[s]=G
  4. 当m=1时，我们可以在初始时直接将f数组全部赋为⌈n3+1⌉（并不懂得m = 2的命令怎么用……）
  5. 记数组mth[i][j]表示选取两点i,j确定抛物线能消灭多少个点，同样用二进制数存储，考虑到mth[i][j]中可能包含一些之前已经被消灭的点，合并状态时应为(s&mth[i][j])+(s|mth[i][j])
  6. 改变搜索顺序：先搜索两点确定抛物线的做法，然后再搜索单独消灭一点。一般情况下这样会先计算出较优的解，以避免不优解的重复搜索
• 最后的答案即为f[2n−1]

注意

• UOJ有特殊点专门卡精度，以下为在UOJ提交的AC代码，注意long_double的使用和eps的取值

代码

#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;
typedef long double ld;
const ld eps = 1e-10;
const int Maxn = 0x3f3f3f3f;
const int N = 20;
ld x[N], y[N]; int n, T, m;
int f[(1 << 20) + 5], mth[N][N];

inline void CkMin(int &a, const int &b) {if (a > b) a = b;}

inline void Dfs(const int &t, const int &G, const int &s)
{
    if (G >= f[s]) return ; f[s] = G;
    if (s == ((1 << n) - 1)) return ;
    for (int i = t; i < n; ++i)
    if (!(s & (1 << i - 1)))
    { 
        for (int j = i + 1; j <= n; ++j) 
        if (!(s & (1 << j - 1)))
        {
            if (!mth[i][j]) continue;
            Dfs(i + 1, G + 1, (s & mth[i][j]) + (s | mth[i][j]));
        }       
    } 
    for (int i = t; i <= n; ++i)
     if (!(s & (1 << i - 1)))
      Dfs(i + 1, G + 1, s | (1 << i - 1));
}

inline int get()
{
    char ch; int res = 0; 
    while ((ch = getchar()) < '0' || ch > '9');
    res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
     res = (res << 3) + (res << 1) + ch - '0';
    return res; 
}

inline void put(int x)
{
    if (x > 9) put(x / 10);
    putchar(x % 10 + 48);
}

int main()
{
    T = get();
    while (T--)
    {
        n = get(); m = get();
        if (m & 1) for (int i = 0; i < (1 << n); ++i) f[i] = ceil((ld)n / 3.0 + 1);
         else memset(f, Maxn, sizeof(f));
        for (int i = 1; i <= n; ++i) scanf("%Lf %Lf", &x[i], &y[i]);
        for (int i = 1; i < n; ++i)
         for (int j = i + 1; j <= n; ++j)
         {  
            mth[i][j] = 0;
            ld a = (y[i] / x[i] - y[j] / x[j]) / (x[i] - x[j]),
               b = y[i] / x[i] - a * x[i];
            if (a >= -eps) continue;
            for (int k = 1; k <= n; ++k)
             if (fabs(a * x[k] * x[k] + b * x[k] - y[k]) < eps) 
              mth[i][j] |= (1 << k - 1);
         }
        Dfs(1, 0, 0); put(f[(1 << n) - 1]), putchar('\n');
    }
}