题解：P2831 [NOIP 2016 提高组] 愤怒的小鸟

· · 题解

前置知识：

题意简述

给定 n 个平面直角坐标系上的点。你可以从原点引出解析式为 y = ax^2+bx(a<0) 的抛物线，问最少引出多少条这样的抛物线，能使得所有给定的点都在这些抛物线上。

具体思路

注意到 n\le18、0<x_i,y_i<10，一切数据范围都指向了搜索和状态压缩 dp。\ 这里考虑使用状压 dp 求解。

dp 部分

设 dp_{state} 表示达到点被覆盖的状态为 state 时所需要的最少抛物线数。其中 state 的第 i 位为 1 表示第 i 个点已经被经过了，为 0 则反之。答案即为 dp_{2^n-1}。

这里我们可以先简化一下题目。我们可以假设所有可以覆盖到点的抛物线已经被求出，经过的点集（经过状压）存储在 line 数组中。\ （其中，line_i 表示第 i 条抛物线经过点的状态。line_i 的第 i 位为 1 表示第 i 个点被这条线经过，为 0 则反之。）

那么我们可以顺推，枚举每一种可能的点被经过的状态 i，再枚举每条可能的抛物线 j 去经过更多点（或者重复了，没有经过新的点）。如果有收益，则使用这条线去更新状态。即：

dp_{i \operatorname{or} line_j} = \min(dp_i+1, dp_{i \operatorname{or} line_j})

但是，有些时候一些点可能无法与原点和另一个点确定一条符合题意的抛物线，却可以直接用一条抛物线去经过这个点。所以，我们还要枚举每一个点（设此点为第 j 个点），专门用一条线去经过。这条线的状态为 {\underbrace{1000\dots0_{(2)}}_{\scriptsize j\text{ 位}}}，也就是 2^{j-1}。即：

dp_{i \operatorname{or} 2^{j-1}} = \min(dp_i+1, dp_{i \operatorname{or} 2^{j-1}})

两者分开转移即可。

不过，如果基于这种做法，是要求出 line 数组的值的。

预处理部分

众所周知，同一平面的三个点可以确定一条抛物线。（本题有了原点，就只用两个点了）\ 所以我们可以枚举每一对点，计算过原点和这两只猪的抛物线的解析式。

不过，我们总不能直接丢一个方程给程序去算吧（是计算器的话当我没说）。所以，我们需要推出 a 和 b 关于 (x_1,y_1),(x_2,y_2) 的式子。

又到了喜闻乐见的推柿子环节。

这里直接给出结论，过程见云剪贴板：

a = \dfrac{y_1x_2 - y_2x_1}{x_1x_2(x_1-x_2)},b = \dfrac{y_2}{x_2} - ax_2

如果 a>0，或者这两点的横坐标相同（x_1=x_2 时，分母为 0），那么这条抛物线不合法，不统计。

对于每条合法的抛物线，枚举给定的每个点 k，并代入函数解析式中。如果经过，就将代表这个点的这一位数设为 1。

最后 dp 一下就可以了。回答单次询问的时间复杂度为 O(n2^n)，可过。

最后的最后，由于处理 line 数组的时候涉及浮点数运算，难免会有误差，所以不能直接用等于号判等。当两个浮点数的差的绝对值小于一个很小的正数时（这里我用了 10^{-6}），我们可以直接认为二者相等。

代码

#include <iostream>
using namespace std;
using ll = long long;
//#define debug cout << "fnmdp"

int dp[262200]; // dp_s 表示点（猪猪）被穿过的情况为 s
int T, n, m, line[10010], cnt;
double xx[20], yy[20];
const double eps = 1e-6;

int main(){
    cin.tie(0) −> sync_with_stdio(0);
    cin >> T;
    while(T −−){
        memset(line, 0, sizeof line);
        memset(dp, 0x66, sizeof dp); // 多测必初始化！！！
        cin >> n >> m;
        for(int i=1; i<=n; ++i){
            cin >> xx[i] >> yy[i];
        }
        for(int i=1; i<=n; ++i){
            // line_i 表示第 i 个函数图像覆盖点的情况
            for(int j=i+1; j<=n; ++j){
                if(xx[i] != xx[j]){
                    double a = (yy[i] − yy[j] * xx[i] / xx[j]) / xx[i] / (xx[i] − xx[j]);
                    double b = yy[j] / xx[j] − a * xx[j];
                    if(a < 0){
                        ++ cnt;
                        for(int k=1; k<=n; ++k){ // 算出解析式后重新枚举
                            if(fabs(a * xx[k] * xx[k] + b * xx[k] − yy[k]) <= eps){
                                line[cnt] |= (1 << (k−1));
                            }
                        }
                    }
                }
            }
        }
        dp[0] = 0;
        for(int i=0; i<(1<<n); ++i){ // dp_i 单调不降，从小到大枚举状态数字
            for(int j=1; j<=cnt; ++j){
                dp[i | (line[j])] = min(dp[i] + 1, dp[i | (line[j])]);
            } // 用一条线覆盖 / 维持原样
            for(int j=1; j<=n; ++j){
                dp[i | (1 << j-1)] = min(dp[i] + 1, dp[i | (1 << j-1)]);
            }
        }
        cout << dp[(1<<n) − 1] << '\n';
    }
    return 0;
}

已防抄袭，请勿直接 Copy。

感谢所有审核大大们！\ End.