题解：CF2038L Bridge Renovation

· · 题解

考虑如何尽量利用长度为 60 的木板。

不难发现，最佳的利用方式为：

其他的方案一定劣于以上三种方案。

继续思考，观察到可以通过 7 根长度为 60 的木板裁出长度为 18、21、25 的木板各 6 根，此时最优。

方案为：(21 + 21 + 18) \times 3 + (25 + 25) \times 3 + (18 + 18 + 18) \times 1

则对于每 6 组木板，我们都会使用 7 根长度为 60 的木板，且这一定是最优的。

那么剩下的 0 \sim 5 组也不难通过模拟得到：

  1. 裁出 1 组需要 2 根；
  2. 裁出 2 组需要 3 根；
  3. 裁出 3 组需要 4 根；
  4. 裁出 4 组需要 5 根；
  5. 裁出 5 组需要 6 根。

那么答案显而易见，为 \lfloor \frac{n}{6} \rfloor \times 7 + a_{n \bmod 6}，其中 a_i 为模拟得到的根数。

进一步化简可以得到最终答案为：n + \lceil \frac{n}{6} \rceil。

本文来自：

另附官方题解。