专栏文章

题解：CF2038L Bridge Renovation

MMournInk
CF2038L题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir377on
此快照首次捕获于
2025/12/04 15:00
3 个月前
此快照最后确认于
2025/12/04 15:00
3 个月前
查看原文
考虑如何尽量利用长度为 6060 的木板。
不难发现，最佳的利用方式为：
  • 21+21+18=6021 + 21 + 18 = 60
  • 18+18+18=5418 + 18 + 18 = 54
  • 25+25=5025 + 25 = 50
其他的方案一定劣于以上三种方案。
继续思考，观察到可以通过 77 根长度为 6060 的木板裁出长度为 1818、2121、2525 的木板各 66 根，此时最优。
方案为：(21+21+18)×3+(25+25)×3+(18+18+18)×1(21 + 21 + 18) \times 3 + (25 + 25) \times 3 + (18 + 18 + 18) \times 1
则对于每 66 组木板，我们都会使用 77 根长度为 6060 的木板，且这一定是最优的。
那么剩下的 0∼50 \sim 5 组也不难通过模拟得到：
  1. 裁出 11 组需要 22 根；
  2. 裁出 22 组需要 33 根；
  3. 裁出 33 组需要 44 根；
  4. 裁出 44 组需要 55 根；
  5. 裁出 55 组需要 66 根。
那么答案显而易见，为 ⌊n6⌋×7+an mod 6\lfloor \frac{n}{6} \rfloor \times 7 + a_{n \bmod 6}，其中 aia_i 为模拟得到的根数。
进一步化简可以得到最终答案为：n+⌈n6⌉n + \lceil \frac{n}{6} \rceil。
本文来自： 做干净的奥赛
另附官方题解。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...