1 条题解
-
0
【2021年省赛B组】试题G: 砝码称重
题解
🎉️ 动态规划,表示每个砝码的三种状态为加、减、不放, 假设题目条件简化一下,只能放一边,你会发现这不就是简单的背包吗,每个物品选和不选,最最简单的动态规划01背包的问题。
👀️ 现在考虑能放俩边的情况,我们能不能在放一边的情况下计算呢?
假设我们放一边的时候是不放和放的情况,那么我们跑完01背包以后怎么加上减这种情况呢?
🚀️ 其实有个很巧妙的做法,就是把不放和加做完计算以后当成一种状态,那么和减的情况当成01背包的俩种状态,如果你这个砝码用的是加的这个状态,那么减去就相当于不放, 如果上次计算的状态是不放, 那么减就是减去这个砝码的重量, 相当于放在天平的另一边,这样不存在重复和漏算的情况了。
😄 结尾:顺便提一下,如果你对的库熟悉的话,可以用这个简单粗暴的工具直接模拟!结尾附上代码。
提交代码
- 基础版本
- 进阶版本
- 1
信息
- ID
- 982
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 11
- 已通过
- 5
- 上传者