「JOI 2014 Final」IOI 馒头 题解

问题分析

我们有 $M$ 个馒头，每个馒头价格 $P_i$，还有 $N$ 种包装盒，第 $j$ 种盒子容量为 $C_j$，成本为 $E_j$。目标是通过选择一些盒子来包装馒头，使得总利润最大化。

关键观察：

• 利润 = 售出馒头总价 - 使用盒子的总成本
• 每个盒子可以装多个馒头，但一个馒头只能装在一个盒子里
• 可以不使用所有馒头，也可以不使用所有盒子

解题思路

1. 贪心策略

由于我们希望最大化利润，应该优先使用价值最高的馒头。因此：

• 将馒头按价格降序排序
• 计算前缀和 $sum[i]$ 表示前 $i$ 个最贵馒头的总价值

2. 动态规划建模

我们将问题转化为：找到最优的盒子组合，使得用最小成本包装 $k$ 个馒头（$0 \leq k \leq M$），然后利润就是 $sum[k] - 成本$。

定义：

• $dp[i]$ = 包装恰好 $i$ 个馒头的最小盒子成本
• 初始状态：$dp[0] = 0$（不包装任何馒头成本为0），其他为无穷大

3. 背包问题转移

对于每种盒子 $(C_j, E_j)$，我们进行背包更新：

对于 j 从 m 到 0:
    dp[min(m, j + C_j)] = min(dp[min(m, j + C_j)], dp[j] + E_j)

这里 $min(m, j + C_j)$ 确保不会超过馒头总数。

4. 计算最终答案

对于每个可能的包装数量 $i$（$0 \leq i \leq m$）：

ans = max(ans, sum[i] - dp[i])

这表示：如果我们选择包装前 $i$ 个最贵的馒头，利润就是这些馒头的总价值减去包装成本。

代码详解

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    vector<int> a(m);
    
    // 读入馒头价格
    for (auto &x : a)
        scanf("%d", &x);
    
    // 将馒头按价格降序排序（优先使用贵馒头）
    sort(a.begin(), a.end(), [&](const int &x, const int &y) {
        return x > y;
    });
    
    // 计算前缀和：sum[i] = 前i个最贵馒头的总价值
    vector<int> sum(m + 1);
    for (int i = 1; i <= m; i++)
        sum[i] = sum[i - 1] + a[i - 1];
    
    // dp[i] = 包装i个馒头的最小盒子成本
    vector<int> dp(m + 1, inf);
    dp[0] = 0;  // 包装0个馒头成本为0
    
    // 处理每种盒子
    for (int i = 1; i <= n; i++) {
        int c, p;
        scanf("%d %d", &c, &p);
        
        // 01背包更新：从后往前避免重复使用同一盒子
        for (int j = m; j >= 0; j--) {
            if (dp[j] != inf) {
                int nxt = min(m, j + c);
                dp[nxt] = min(dp[nxt], dp[j] + p);
            }
        }
    }
    
    // 计算最大利润
    int ans = 0;
    for (int i = 0; i <= m; i++) {
        if (dp[i] != inf) {
            ans = max(ans, sum[i] - dp[i]);
        }
    }
    
    printf("%d\n", ans);
    return 0;
}

算法正确性证明

1. 贪心正确性

由于所有馒头互不相同且价格固定，显然应该优先包装价值高的馒头来最大化收入。

2. 动态规划正确性

• $dp$ 数组正确计算了包装任意数量馒头的最小成本
• 通过从后往前更新，确保每个盒子只使用一次（01背包）
• $min(m, j + C_j)$ 确保不会超过馒头总数

3. 答案计算正确性

对于每个 $i$，$sum[i] - dp[i]$ 表示包装前 $i$ 个最贵馒头所能获得的利润，取最大值即为答案。

复杂度分析

• 排序馒头：$O(M \log M)$
• 计算前缀和：$O(M)$
• 动态规划：$O(N \times M)$
• 总复杂度：$O(M \log M + N \times M)$

在数据范围 $M \leq 10^4$，$N \leq 500$ 下，总操作量约为 $5 \times 10^6$，可以接受。

示例验证

样例1

馒头：$[190, 180, 170, 160]$（已排序） 前缀和：$sum = [0, 190, 370, 540, 700]$

通过DP找到最优方案：

• 包装2个馒头：成本100，利润 $370-100=270$
• 包装4个馒头：成本 $100+120=220$，利润 $700-220=480$

最大利润为480，符合样例输出。

总结

本题通过贪心排序和背包DP的结合，巧妙地解决了馒头包装的利润最大化问题。关键在于将原问题转化为：用最小成本包装前 $k$ 个最贵馒头，然后遍历所有 $k$ 找到最大利润。