[NOIP2016 提高组] 愤怒的小鸟题解

题目链接

题目大意

题目描述

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

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

有一架弹弓位于

当小鸟落回地面（即

在游戏的某个关卡里，平面的第一象限中有

如果某只小鸟的飞行轨迹经过了

如果一只小鸟的飞行轨迹没有经过

例如，若两只小猪分别位于

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

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

这些指令将在输入格式中详述。

假设这款游戏一共有

由于她不会算，所以希望由你告诉她。

注意:本题除 NOIP 原数据外，还包含加强数据。

输入格式

第一行包含一个正整数

下面依次输入这

每个关卡第一行包含两个非负整数

接下来的

如果

保证

上文中，符号

输出格式

对每个关卡依次输出一行答案。

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

数据范围

QQ截图20210311115727.png

输入样例

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

题解

先来说一下做这道题的时候是十一点十五

想了一会儿开始调题，结果调了半天都不对，有几个地方zz了

然后都五十分了机房其他同学都已经吃完饭上来了，我才刚调完。

下去去食堂人挤人，好饿

吃完饭回来又飞快（巨慢）的打了一遍，总算是过了

来说一下思路吧

由于抛物线的解析式只有两个参数，所以只需要两个点就可以确定一条抛物线，对于 n 个点来说，最多有 n ²条抛物线

我们不妨把这些抛物线先预处理出来，同时预处理出来每一条抛物线包含的点集

这是我们发现问题变成了一个经典的“重复覆盖问题”，也就是给定一个01矩阵，选择数量最少的行，覆盖所有列

这个问题的标准做法是 Dancing Links

由于n 不超过18，所以这道题可以考虑用状压dp；

f[i] 表示当前已经覆盖的列是i时的最小行数。

转移时随便找到当前未被覆盖的某一列 xx，然后枚举所有包含 xx 的行j来选择即可。

即：f[i | j] = min(f[i | j], f[i] + 1)。

最后来分析一下时间复杂度

首先预处理抛物线及其覆盖点集需要枚举复杂度为O(n³)；

状态压缩DP的过程中，一共有 2ⁿ个状态，每个状态需要 O(n)的计算量

最后的时间复杂度总计为 O(T(n³+n²ⁿ))。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define x first
#define y second

using namespace std;
const int N = 18,M = 1 << 18;
const double eps = 1e-8;

int m,n;
typedef pair<double,double> PDD;
PDD q[N];
int f[M];
int path[N][N];

int cmp(double x,double y)
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}


int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        cin >> n >> m;
        for(int i = 0; i < n; ++ i) cin >> q[i].x >>q[i].y;
        memset(path,0,sizeof path);
        for(int i = 0; i < n; ++i)
        {
            path[i][i] = 1 << i;
            for(int j = 0; j < n; ++ j)
            {
                double x1 = q[i].x,y1 = q[i].y;
                double x2 = q[j].x,y2 = q[j].y;
                if(!cmp(x1,x2)) continue;
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                if(cmp(a,0) >= 0) continue;
                double b = y1 / x1 - a * x1;
                int state = 0;
                for(int k = 0; k < n; ++ k)
                {
                    double x= q[k].x,y = q[k].y;
                    if(!cmp(a * x * x + b * x,y)) state += 1 << k;
                }
                path[i][j] = state;
            }
        }
        
        memset(f,0x3f,sizeof f);
        f[0] = 0;
        for(int i = 0; i + 1 < 1 << n; ++ i)
        {
            int x = 0;
            for(int j = 0; j < n; ++ j)
              if(!(i >> j & 1)) 
              {
                  x = j;
                  break;
              }
            for(int j  = 0; j < n; ++  j)
              f[i | path[x][j]] = min(f[i | path[x][j]],f[i] + 1);
        }
        cout << f[(1 << n) - 1] << endl;
    }
    return 0;
}

[NOIP2016 提高组] 愤怒的小鸟 题解