ACGO巅峰赛#22+题解

解题思路

1. 问题分析
   小 M 每次购买两件不同种类的商品，预算为 $m$ 元。小 P 收下两件中幸福度较低的那件。目标是最大化小 P 获得的幸福度总和。

2. 关键点

   • 两件商品价格和不能超过预算 $m$。
   • 小 P 取两件中幸福度较低的那件，意味着每次购买的幸福度收益是两件中较小的幸福度。
   • 每种商品可无限购买，且每次选购的两件商品种类不同。

3. 转化思路

   • 按幸福度从高到低排序商品。
   • 设当前商品为 $i$，其幸福度为 $v_i$，价格为 $c_i$。
   • 由于小 P 取较低幸福度的商品，若当前商品的幸福度为 $v_i$，搭配的另一种商品幸福度必定至少 $v_i$。
   • 因此，购买两件商品中小 P 获得的幸福度是 $v_i$。
   • 对于当前商品，找到之前价格最小的商品，计算两者价格和 $c_i + c_{min}$，若不超过预算 $m$，则可以购买。
   • 使用动态规划维护在预算 $m$ 下小 P 最大幸福度。

4. 动态规划设计

   • 令 $dp[k]$ 表示预算为 $k$ 时小 P 能获得的最大幸福度总和。
   • 对每个商品 $i$，尝试用它和之前找到的价格最小商品配对，更新可达的预算状态。
   • 最终答案为 $dp[m]$。

---

代码解释

#include <bits/stdc++.h>
using namespace std;

void setup_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
struct Item {
    int c, v;
};
bool compareItems(const Item& a, const Item& b) {
    if (a.v != b.v) {
        return a.v > b.v;
    }
    return a.c < b.c;
}
int main() {
    setup_io();
    int n;
    long long m;
    cin >> n >> m;
    vector<Item> items(n);
    for (int i = 0; i < n; ++i) {
        cin >> items[i].c >> items[i].v;
    }
    sort(items.begin(), items.end(), compareItems);
    vector<long long> dp(m + 1, 0);
    int min_cost_so_far = 20001;
    for (int i = 0; i < n; ++i) {
        int current_cost = items[i].c;
        int current_value = items[i].v;
        long long pair_cost = (long long)current_cost + min_cost_so_far;
        if (pair_cost <= m) {
            for (long long k = pair_cost; k <= m; ++k) {
                dp[k] = max(dp[k], dp[k - pair_cost] + current_value);
            }
        }
        min_cost_so_far = min(min_cost_so_far, current_cost);
    }
    cout << dp[m] << '\n';
    return 0;
}