解题思路 1. 问题分析 小 M 每次购买两件不同种类的商品，预算为 mmm 元。小 P 收下两件中幸福度较低的那件。目标是最大化小 P 获得的幸福度总和。 2. 关键点 * 两件商品价格和不能超过预算 mmm。 * 小 P 取两件中幸福度较低的那件，意味着每次购买的幸福度收益是两件中较小的幸福度。 * 每种商品可无限购买，且每次选购的两件商品种类不同。 3. 转化思路 * 按幸福度从高到低排序商品。 * 设当前商品为 iii，其幸福度为 viv_ivi ，价格为 cic_ici 。 * 由于小 P 取较低幸福度的商品，若当前商品的幸福度为 viv_ivi ，搭配的另一种商品幸福度必定至少 viv_ivi 。 * 因此，购买两件商品中小 P 获得的幸福度是 viv_ivi 。 * 对于当前商品，找到之前价格最小的商品，计算两者价格和 ci+cminc_i + c_{min}ci +cmin ，若不超过预算 mmm，则可以购买。 * 使用动态规划维护在预算 mmm 下小 P 最大幸福度。 4. 动态规划设计 * 令 dp[k]dp[k]dp[k] 表示预算为 kkk 时小 P 能获得的最大幸福度总和。 * 对每个商品 iii，尝试用它和之前找到的价格最小商品配对，更新可达的预算状态。 * 最终答案为 dp[m]dp[m]dp[m]。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码解释

礼物 题目大意 你现在有 mmm 元钱，现在有 nnn 中不同的物品。每种物品有一个花费 cic_ici 和幸福值 viv_ivi ,你每次可以购买两个不同的物品，你的朋友会收下幸福度较低的一个，问你的朋友最大可以获得多少幸福度 题解思路 我们希望找到所有幸福值大于等于自己的元素中花费最少的应该是多少，这样我们可以先按照幸福值进行排序，之后我们可以用一个类似于前缀最小值的方法找到相应的花费，活着直接枚举也可以。 问题就转换为一个 nnn 个物品， mmm 点花费的完全背包。 参考代码

首先 O(n2m)O(n^2m)O(n2m) 的暴力转移 DP 非常好写，不再说明。考虑优化 DP。 容易想到，每一次购买是独立的，相互不依赖、不影响。所以可以预处理一下。 预处理出进行一次购买，花费为 iii 时候，小 P 所能拿到的最大价值。这个过程 O(n2)O(n^2)O(n2) 枚举即可。 然后就是朴实无华的完全背包了。 时间复杂度：O(n2+m2)O(n^2+m^2)O(n2+m2). 空间复杂度：O(n+m)O(n+m)O(n+m). Code: