BalticOI 2022 D1T3 Uplifting Excursion 题解
First Post:
Last Update:
Last Update:
感觉今年的 BalticOI 较为简单(除通信题)。就 2022 年这套题来说,是有训练价值的,但并没有非常难的题。
题意传送门: https://loj.ac/p/3776
注意到这题要我们做个类似背包的东西,但是所有物品价值为
先说
看到这种目标体积远大于单个物品体积的题,容易想到先用贪心尝试逼近那个目标体积。在贪心时,我们显然倾向于选体积更小的物品,这样能选的物品更多。贪心时在不超过
在贪心解的基础上,我们考虑用 DP
凑出这个剩余部分。此时有一部分物品要新增,有一部分已经选的物品要撤销,我们称这种过程为调整。我们可以证明,调整的总次数不超过
证明:我们可以贪心地排列调整的顺序,使得调整序列中每处的前缀和都在
因此,调整的物品的总体积是
上文假设没有体积为负的物品,实际上有体积为负的物品也区别不大。我们可以将体积为负的物品强制选取,然后再尝试撤销这些物品。这样所有物品的体积和
于是本题就做完了,时间复杂度
C++ - 61 lines
expand
1 |
|
Gitalking ...