ABC351E

cf想上橙，但没办法all in算法，所以进行复盘，多注重思维积累

刷题记录 2

dp

ABC373F

link：https://atcoder.jp/contests/abc373/tasks/abc373_f

在裸的完全背包上加了个条件：如果购买了 个相同物品，会有 的价值损失。

尝试先用正常的dp：记 为考虑前 个物品，用了 个容量的答案。

显然有转移 ，时间复杂度是 ，如果 全为1就是 级别的。

因此我们可以考虑将dp的第一维用单个物品容量来代替。记 为考虑单个容量不超过 的物品，用了 个容量的答案。

转移一样是 ，即考虑单个容量为 的物品的贡献，时间复杂度是 。

但是这里有个问题，就是单个容量为 的物品可能不是唯一的。假设对于容量为 的物品有两件，我们在dp转移枚举 (即购买两件物品)的时候，可能是购买同一个物品两件，也可能两件物品各购买一件，而这两种情况显然是不一样的，我们需要取最优。

因此我们将转移方程写为 ，这里的 为考虑购买 个容量为 个物品时对于答案的最优贡献。

怎么算这个 呢？第一反应是从 进行转移，当然这种想法是正确的。

假设我们从 转移到 ，且容量为 的物品有两件，记为a和b。而对于 ，我们假设它是购买了三个a，两个b。

我们转移到 时，就应该需要知道购买第四个a和第三个b时，二者分别对答案的贡献。购买第k件同一个物品时该物品的贡献为 （做个差分就行了）。这个东西（显然）是单调递减的，因此可以采用贪心策略：

• 首先我们先算出所有单个容量为 的物品在 时对答案的贡献。
• 搞个大顶堆，将这些答案以及对应的 放进去。然后开始计算 ，每次从大顶堆取出答案时，根据取出的答案对应的 ，计算出该物品取 的贡献，重新插到堆里。

Code：https://atcoder.jp/contests/abc373/submissions/59299326

总结：本题的突破口在于将传统的背包dp中枚举第几个物品转换为枚举单个物品的容量，同时还要在意到该题购买同一个物品时其对答案的贡献是单调递减的（从数学上来讲，就是 对 的二阶导为非正，因此你可以在出类似于校内新生赛的时候把这个式子改一改，从而转换成自己的题（不是）），如果不是单调递减的话那么贪心策略就是错的。

graph

misc