$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题问的是，给定 $n$ 个点，最少需要多少条抛物线才能将它们全部覆盖

$N$ 只有 18 ，基本就是暴搜和状压没跑了

我们自顶向下考虑 DFS 函数的设计

    void DFS(int state, int cnt)//state表示二进制状态，即某一位的点是否被抛物线覆盖
    {                           //cnt表示当前状态中抛物线的条数
        if(state 全被覆盖) 
        {
            ans = max(ans, cnt);//ans为全局变量
            return;
        }
        任取当前没有被抛物线覆盖的点t(state对应位置为0的点)
        遍历其余点j，由t和j组成一条抛物线
        将新抛物线加入到state中，并cnt++
        DFS(new_state, cnt + 1);
    }

这里我们需要考虑的问题是：$new \underline{ } state$ 的状态如何更新？

由于 $state$ 当中表示的是每个点是否被抛物线覆盖，因此如果我们用一条新的抛物线来更新时，需要知道这条新抛物线穿过的所有点（同样用二进制数表示）

由于两个点就可以组成一条抛物线，因此我们在此预处理出来所有抛物线通过的点，并将其全部用二进制表示

我们用 $path[i][j]$ 表示由点 $i$ 和点 $j$ 构成的抛物线所穿过的点

例如：$path[2][3]=100111$ ，表示编号为 2 和 3 组成的抛物线穿过了编号为 1，2，3，6 的点

由于 $path[i][j]$ 的表示与 $state$ 的表示相同，因此有 $new\underline{ }state=state\ \| \ path[i][j]$

DFS 函数只是为了帮助我们思考，我们并不需要实际写出来

我们定义 $f[i]$ 表示在状态 $i$ 下最少的抛物线数，有 $f[new\underline{ }state]=max(f[new\underline{ }state],\ f[state]+1)$

最后输出 $f[(1<<n)-1]$ ，减一是因为 $1<<n$ 使得权重达到 $2^n$ 了，我们需要的最大权重为 $2^{n-1}$

完整代码：

#include <iostream>
#include <cstring>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 20, M = 1 << 18;
const double esp = 1e-8;

PDD q[N];//存储各个点
int f[M], path[N][N];
int n, m;

int cmp(double x, double y)
{
    if(fabs(x - y) < esp) return 0;//因为精度不够，因此需要额外判断
    if(x > y) return 1;
    else return -1;
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        memset(path, 0, sizeof path);
        cin >> n >> m;
        for(int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;

        //预处理阶段
        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);
                double b = y1 / x1 - a * x1;                
                if(cmp(a, 0) >= 0) continue;
                for(int k = 0; k < n; k++)
                {
                    double x = q[k].x, y = q[k].y;
                    if(!cmp(y, a * x * x + b * x))
                        path[i][j] += 1 << k;
                }
            }
        }   

        memset(f, 0x3f, sizeof f);
        f[0] = 0;

        //状态转移
        for(int i = 0; i + 1 < 1 << n; i++)//遍历所有状态
        {
            int t = -1;
            for(int j = 0; j < n; j++)//找到第一个不被抛物线覆盖的点
                if(!(i >> j & 1))
                    t = j;

            for(int j = 0; j < n; j++)
                f[i | path[t][j]] = min(f[i | path[t][j]], f[i] + 1);
        }

        cout << f[(1 << n) - 1] << endl;
    }

    return 0;
}