首页 > 大魔法师牛可乐
开通博客写题解
头像 在刷题的单身狗很开心
发表于 2023-10-18 16:39:31
本题得知道一个结论，如果序列里面的数的最大公约数为1的话就一定可以到达任意一个魔法阵。 那么就对最大公约数进行动态规划。以每个数为外层循环。每一次都与前面有的或产生的数进行最大公约数的计算，然后更新某个数作为最大公约数所需要的花费即可。 //对于某一个数 它的加入对原来产生的 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Peterhuang98
发表于 2024-06-20 13:11:54
这题用dfs其实更好理解： 核心idea就是找一个组合，他们的gcd为1。 由于需要排序的数量不大，就300左右，其实把cost进行排序然后剪枝应该更快一些的 注意dfs时不要忘了一开始的for循环，我就是上来写的dfs只从0开始一直不过，才忘记自己没有设置根结点，需要手动遍历最开始的一层（如果序号 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”