【题解】「Public NOIP Round #2」找零

[官解](Public NOIP Round #2 题解 - 博客 - Qingyu的博客 (pjudge.ac))

Tag： 背包、dp 凸优化

决策点单调触碰到知识点盲区了，所以来写几笔。

首先，由于我们只关心最终状态下 \(1\) 的最多个数，其实有用的面值只有 \(5,1\)（其她的可以当成若干个 \(5\) 来使用。

显然初始的 \(1\) 我们是不用的，于是现在问题转化为：

初始答案 \(ans\gets m-5\left\lfloor\dfrac m5\right\rfloor\)。

然后，\(m\gets m-ans\)。

现在每个物品 \((a,w)\) 变为：

• 价值：\(w\gets 5\left\lceil\dfrac a5\right\rceil-a\)；
• 体积：\(a\gets a+w\)。

现在问题就是一个 类 0-1 背包了。

为什么说是 类？

因为，这道题的价值的范围只有 \([0,4]\)，而体积很大，所以用一个叫做「值和状态反转」的 trick（自己瞎取名。

标签：NOIP,题解,找零,Round,价值,Public,单调
From： https://www.cnblogs.com/CloudWings/p/18425513