首页 > 我不是大富翁
开通博客写题解
头像 刘来也
发表于 2024-03-09 00:09:10
菜鸟一个，写个个人代码题解 下面的部分都是本人的个人理解，如果有错误，请大家斧正。 首先，这道题目可以理解为解决这么一个问题：如果我们想让Rabbit的最终位置在1保持不变，那么此时我们这样思考，我们现在假设Rabbit现在已经到达了最终的目的地同时还是1这个位置，也就是保持不动，那么我们可以到达这 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 Rain_Fly
发表于 2024-03-08 22:54:56
一个dp问题 dp[i][j]表示从第i次可以到达距离为j的位置（dp[i][j] = 1） 如果dp[i-1][j] = 1,就从这个位置计算下一次可能到的位置 最后判断dp[m][0]是否为1，注意dp[m][0]表示m次仍在1号位置（j代表着相对位移） #include 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 hqztrue1
发表于 2024-03-09 00:24:24
注意到这是一个 Modular Subset Sum 模板题。算法参见 SOSA'21 的这两篇文章： https://arxiv.org/abs/2008.08417 https://arxiv.org/abs/2008.10577 复杂度 ，可优化到 。 以下是直接从 paper 里抄的模板： 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”