记忆化搜索优化一下，不到100ms

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

typedef pair<double,double> PDD;

const int N = 18, M = 1 << 18;
int f[M]; //f[i]表示覆盖二进制状态i到 111...1需要多少条抛物线
int path[N][N];
PDD pos[N];
int t,n,m;

int cmp(double a,double b) {
    if(abs(a-b) < 1e-6) return 0;
    if(a>b) return 1;
    return -1;
}

//计算覆盖二进制状态state到 111...1需要多少条抛物线,并保存在f[state]中
int dfs(int state) {
    if(state + 1 == 1 << n) return 0;
    if(f[state]) return f[state];//若已经计算过，直接返回，避免重复计算
    int t;
    for(int i=0;i<n;i++) {
        if(!(state >> i & 1)) {
            t = i;
            break;
        }
    }
    int res = n*n;
    for(int i=0;i<n;i++) {
        if(!path[t][i]) continue;//避免死循环
        res = min(res,dfs(state | path[t][i]) + 1);
    }
    return f[state] = res;
}

int main() {
    cin >> t;
    while(t--) {
        cin >> n >> m;

        for(int i=0;i<n;i++) cin >> pos[i].first >> pos[i].second;
        memset(path,0,sizeof path);
        for(int i=0;i<n;i++) {
            path[i][i] = 1 << i;
            for(int j=i;j<n;j++) {
                double x1 = pos[i].first, y1 = pos[i].second;
                double x2 = pos[j].first, y2 = pos[j].second;
                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 = pos[k].first, y = pos[k].second;
                    if(!cmp(a*x*x + b*x,y)) path[i][j] += 1 << k;
                }
            }
        }

        memset(f,0,sizeof f);
        cout << dfs(0) << endl;
    }
    return 0;
}

感谢楼主提供的记搜思路，对比递推快了10倍左右
然后在楼主的基础上，我加了一些小优化，从最开始的97ms优化到了85ms
优化点如下：
1.递归边界也进行记忆化

 if(state + 1 == 1 << n) return f[state]=0;

2.comp数组用fabs，好像快了几ms
3.如下图参考洛谷题解

顺便贴一下很多人不太理解的中途break，那篇洛谷题解也说明了，其实是一个复杂度优化

下面是完整的优化后代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<double,double> PDD;
const int N = 18 , M=101, MOD = 1e8 ,INF=0x3f3f3f3f;
const double eps = 1e-8;

PDD pos[N];
int cover[N][N];    //cover[i][j]表示i和j号猪组成的抛物线可以覆盖的点集
int n,m,dp[1<<N];

int comp(double a,double b)     //比较两个浮点数
{
    if(fabs(a-b)<eps) return 0;
    else if(a>b) return 1;
    return -1;
}

int dfs(int state)      //dp[i]:从状态i覆盖完所有点最少需要多少
{
    if(state+1==(1<<n)) return dp[state]=0;
    if(dp[state]) return dp[state];

    int ret=n*n;

    int t=0;

    for(int i=0;i<n;i++)
    {
        if(!(state&(1<<i)))         //如果还有未覆盖的点
        {
            t=i;
            break;
        }
    }

    for(int i=0;i<n;i++)
    {
        if(!cover[t][i]) continue;      //细节，如果这个点和t无法构成抛物线的话，递归这个状态会导致死循环
        if(state&(1<<i)) continue;
        ret = min(ret,dfs(state|cover[t][i])+1);
    }

    return dp[state] = ret;
}

void process()
{
    memset(cover,0,sizeof(cover));
    for(int i=0;i<n;i++)
    {
        cover[i][i]=(1<<i);         //自己和自己可以覆盖
        for(int j=i;j<n;j++)    //枚举两个点构成的抛物线
        {
            double x1 = pos[i].first,x2 = pos[j].first;
            double y1 = pos[i].second,y2 = pos[j].second;

            if(!comp(x1,x2)) continue;      //这里特判很容易漏，如果不特判的话，下面计算a的时候分母x1-x2就是0了

            double a = (y1/x1-y2/x2) / (x1-x2);
            double b = y1/x1-a*x1;

            if(comp(a,0)>=0) continue;      //题目要求抛物线开口向下

            for(int k=0;k<n;k++)        //然后枚举这条抛物线可以覆盖哪些点
            {
                double x=pos[k].first,y=pos[k].second;
                if(!comp(a*x*x+b*x,y))  cover[i][j]|=(1<<k);
            }
        }
    }
}

void solve()
{

    cin>>n>>m;

    for(int i=0;i<n;i++) cin>>pos[i].first>>pos[i].second;

    process();

    memset(dp,0,sizeof(dp));    
    dfs(0);
    cout<<dp[0]<<endl;
}

int main(){

    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin>>T;

    while(T--)  solve();

    return 0;
}

“转移时随便找到当前未被覆盖的某一列 xx，然后枚举所有包含 xx 的行j来选择即可。”为什么是随便找一行即可，而不是遍历所有情况？？？

假设有10个小猪, 现在0, 1, 2都被消灭了, 其他都没有, 在这个状态下, 我们找到第一个未被消灭的小猪编号为3, 此时枚举编号3和另一个小猪(可能来自已消灭的)组成的抛物线, 对应上面的代码就是f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);.

为什么只需要找到第一个未被消灭的小猪即可, 你想一下, 虽然它此时未被消灭, 但是它最后肯定会被某一条抛物线消灭掉, 这是我们相当于枚举这个小猪被那条抛物线消灭掉, 当然这样能找到最优解即答案了.

另外上面的代码是递推的写法, 其实状态压缩的dp, 更常见的是记忆化的写法, 不过也不太重要, 理解过程才是最重要的.

还是不是很懂，这样不会 遗漏第4,5,6,7,8,9,10只猪被没有经过3的抛物线消灭的情况吗

比如一种情况是 4 5 6 7 8 9都在一条抛物线上，3自己在一条抛物线上，这样的话只能找到三，并不能枚举到同时包含4 5 6 7 8 9的这条抛物线，所以0 1 2 4 5 6 7 8 9同时被消灭的状态也就少了一次更新，就不对了？？？

“是它最后肯定会被某一条抛物线消灭掉”,这个我能理解，但是问题是这某一条抛物线未必是最优解的那一条啊，

这里只是随便选择了一条，并没有枚举

枚举在最优解里面这头猪所在的抛物线。

写的真好，懂了！

那么好像枚举到dp[1111000000]时就转移成功了

思想应该是类似bfs,起点dp[0]=0是最优的，由该点出发更新到的点也是最优的，y总在视频里提到了顺序的概念，只找一条应该就是顺序问题

我理解这里 是因为这里找出来的点x 是为了进行下一步的状态转移 而不是为了把没有覆盖的点覆盖上。因为我们枚举了所有的状态，每次找出一个未覆盖的 那最后也自然也能把所有状态都覆盖到。

我悟了
牛蛙

我懂了，就是说枚举的时候总有一次能把某个空的点给补上，就和01背包一样

枚举所有未包含的点和只枚举一个，效果是一样的。枚举所有未被覆盖的点，可以通过。但是时间复杂度是$O(n^2*2^n)$，很有可能超时。所以我是当作一步优化来看的。
1. 最笨的枚举方式，是对于每一个状态都遍历一遍抛物线。
2. 聪明一点，就是只遍历状态中没有的抛物线。
3. 但是这个时候，还是有重复的计算。为什么暂时没想明白…
4. 最后，因为随便找一个未被覆盖的点，到达新的状态，可以保证能够到达这个新状态的所有旧状态一定是不漏的。所以可以这么写。

首先，每次循环都只能把一个小猪加入集合。
由于每一次都增加一个进去。所以不管你是加a还是加上b,都是没有什么关系。
另外path[x][y]就是包含x的所有抛物线，所以不会出现包含x的抛物线，没有被枚举的情况。

可以看成n个点最终是由m条抛物线包围的，那么抛物线之间是没有直接关系的。比如答案是1， 2， 3， 4这四条抛物线吧，那么我们可以在搞出来1之后，只搞出来2，凑成1，2。然后再继续去搞3，4，就没必要搞出来1，2，又要搞1，3这种。我是这样理解的。

因为这样子枚举是包含了所有情况的。假如目前选择了第i行，你可能会觉得我可以选择其他的第j行来更新状态，这样子可以得到一个之前没有的全新状态，但是这个j行也可以在你更新i之后在选择j来更新，结果是一样的，也就是其他同学说的先后不影响的情况

我们本质是遍历所以有的抛物线 ，而不是 遍历所有 该状态 接下来可以转移的 状态
只遍历一个状态中未被覆盖的小猪引出的所有抛物线：
由于我们枚举了所有状态，所以每一只小猪都会作为第一个未被覆盖的小猪
因此会对每一条抛物线进行遍历
所以再去遍历状态中下一只未被覆盖的小猪引出的所有抛物线，会重复遍历抛物线

对path[i][i]=i的理解：
如果没有一个经过其他点抛物线经过他
那么就必须构造这一个反牛顿的直线代替专门经过他的抛物线。
这样转移的时候才算得上他

y总 f[i | path[x][j]] 这里为什么要这样来表示状态转移没看懂

f[i] 表示能覆盖 i 状态的最小抛物线数量。此时的 i 状态，还没覆盖 x 点。path[x][j] = state 是由 (x,j) 点组成的抛物线，一定可以覆盖 x，当然也可能包括其它点，这里二进制意义下就是状态 state。等于说在 f[i] 这些抛物线中再加入 path[x][j] 这条抛物线，则 x 点即被覆盖，当然 path[j][x] 也是可以的。f[i | path[x][j]] 就是将新加入的这条 path[x][j] 抛物线所能覆盖的点和 f[i] 原有这些抛物线所能覆盖的点取并集，二进制下就是 或 运算。在此我个人理解，path[x][j] 是以点 (x, j) 构成的抛物线，保证了 x 一定被覆盖。那么也可能存在 path[a][b] 也能覆盖 x 点，在我们确定点 x，枚举 j 的过程中一定可以将所有穿过 x 点的抛物线枚举到，即 path[a][b] 所构成的抛物线方程是和 path[x][j] 其中一个是完全等价的，则存的状态也是一样的，故全体方案都可以被枚举到。

很清晰

简洁明了

大佬的解释很清晰！

tql

同问：为什么转移时随便找到当前未被覆盖的某一列 xx，然后枚举所有包含 xx 的行j来选择即可，而不是遍历所有情况？？？

f[i]代表的实际意义是什么啊

经过状态为i这么多点的最小所需抛物线

这个代码出了什么问题？

#include [HTML_REMOVED]
using namespace std;

const int N=18, M=1<<18;
const double eps=1e-8;
int n, m;
int path[N][N], dp[M];
pair[HTML_REMOVED] q[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 a=0; a[HTML_REMOVED]>q[a].first>>q[a].second;
}
memset(path, 0, sizeof(path));

    for (int a=0; a<n; a++)
    {
        path[a][a]=1<<a;
        for (int b=0; b<n; b++)
        {
            double x1=q[a].first, y1=q[a].second;
            double x2=q[b].first, y2=q[b].second;
            if (!cmp(x1, x2)) continue;
            double at=(y1/x1 - y2/x2)/(x1-x2);
            double bt=y1/x1-a*x1;

            if (cmp(at, 0)>=0) continue;
            int state=0;
            for (int c=0; c<n; c++)
            {
                double x=q[c].first, y=q[c].second;
                if (!cmp(at*x*x+bt*x, y)) state += 1<<c;
            }
            path[a][b]=state;
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0]=0;
    for (int a=0; a+1<1<<n; a++)
    {
        int x=0;
        for (int b=0; b<n; b++)
        {
            if (!(a>>b &1))
            {
                x=b;
                break;
            }
        }
        for (int b=0; b<n; b++)
        {
            dp[a|path[x][b]]=min(dp[a|path[x][b]], dp[a]+1);
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
}
return 0;

}

markdown炸了

3 月前还没学 markdown 😅

path[i][i] = 1 << i;和state += 1 << k;什么意思，没太懂

path[i][j]表示经过第i个点和第j个点的抛物线所能够覆盖的点集，path[i][i]对经过第i个点和第i个点的抛物线（从原点到第i个点）所能覆盖的点集只有第i个点，1<<j既是对这个点的二进制优化。后者state表示的是当前path[i][j]所能覆盖的点集，如果此时第k个点能够符合情况（在该抛物线上），则将其添加到这个点集上

ok,谢谢

指令m没什么作用吗

没有喔 给oi选手用的

感觉这里不是枚举每一列，而是枚举每一只小猪吧

01矩阵，每一列0/1就是每只小猪能否被预处理的线覆盖

请问为什么有n^2种不同的抛物线呢

双重循环扫描1~n, 获得所有可能能够构成曲线的点对, 这个时间复杂度就是n^2

path[i][i] = 1 << i;不是很理解。

这是为了处理只有一个点的情况。表示穿过点i的直线必然会穿过点i，比较绕口hh

yz我觉得你这里讲错了诶
path[i][j]表示经过第i个点和第j个点的抛物线所能够覆盖的点集，path[i][i]对经过第i个点和第i个点的抛物线（从原点到第i个点）所能覆盖的点集只有第i个点，1<<j既是对这个点的二进制优化。
如果射出的是直线，牛顿爷爷会不高兴的

不对哦，三个点确定一条开口固定的抛物线(本题中是向下，4个点确定一条抛物线)，由于本题中要求开口向下了(重力加速度)，所以对于大多数抛物线来说由三个点((0，0)，i点，j点)确定，但对于每个点i我们会额外加入一条仅由((0,0),i点)确定的点，而两点只能确定一条直线，所以确实是一条穿过i点的直线，当然由于这种特殊情况的线不参与下一重循环所以理解为一条所能覆盖的点集只有第i个点的抛物线也没问题滴

在计算时间复杂度的时候要不要把多组测试数据T乘进去呢yls

要算的，所以本题最后的时间复杂度会多乘一个 $T$。

yls，重复覆盖问题在哪个视频里会单独讲吗？

一般讲dancing links的时候会讲，现在还没单独讲过。

dancing links是哪些题目啊

y总进阶课会讲dancing links吗 很久以前就听说过dancing links 很期待进阶课

数独、八皇后都可以用dlx做。

会讲。

2022回来考古 进阶课数据结构讲了hh 有六道题

yls，所以这个题中m就没有被用到吗？我看到m = 0，1，2还没搞清楚要干什么。。

多余的条件，可以忽略。或许用暴搜的话可以剪枝。

n不是<=18吗？？？

笔误，已修正~

图片是咋发的

这里支持markdown语法，可以先在首页的新鲜事里或者acwing的其他编辑框内把图片传到服务器，然后把链接复制过来，用markdown语法封装好。

哦好的

这题确实较难。提交的人用的全是同一种方法。

是的。在NOIP中也算偏难的题目了。

notin数组没起到任何优化的作用，用的时候完全可以现算。

对滴。写完之后才发现没有优化效果，可以去掉。

请问一下 当状态为i时找到一个未被覆盖的x然后更新其他列 之后就到下一个i+1状态 那么可不可能状态为i的时候另外两个列发射一条曲线会比从任意找的一个x发射曲线情况更优呢

不会的。选择抛物线时的顺序不影响最终结果，x最终需要被覆盖掉，所以一定要选择一条可以覆盖x的抛物线，那么现在选和放在以后选都可以得到相同的最优结果。