题目链接

题目描述

• 有 $M$ 种互不相同的馒头各一个，第 $i$ 个馒头卖 $P_i$ 元。

  有 $N$ 个包装盒，第 $j$ 个包装盒最多能装 $C_j$ 个馒头，买第 $j$ 个包装盒的花费为 $E_j$ 元。要求只能将一些馒头放进包装盒中打包出售，不能零售，当然也可以不出售某些馒头。售出一盒馒头得到的利润为盒内所有馒头的价格减去包装盒的价格。

  现在买下（这 $N$ 个包装盒）其中的一些包装盒（也可以不买，还可以全买），将馒头打包出售，求最大可能利润。

输入格式

第一行两个正整数 $M,N$，意义如题目描述；
接下来 $M$ 行，每行一个正整数 $P_i$，表示第 $i$ 个馒头的价格；
接下来 $N$ 行，每行两个正整数 $C_j,E_j$，表示第 $j$ 个包装盒最多能装 $C_j$个馒头，花费 $E_j$ 元。

对于全部数据，$1 \le M \le 10^4, 1 \le N\le 500, 1 \le P_i,C_j,E_j \le 10^4$。

详细子任务及数据满足条件如下表：

Subtask	追加限制	分值
$1$	$N \le 10$	$25$
$2$	$C_j \le 10$	$35$
$3$	无追加限制	$45$

输出格式

一行一个整数，表示最大可能利润。

题解

贪心的想，既然要求最大利润，应当保证所选的包装盒内装的馒头全部为尽可能售出价格更高的馒头。

问题转换成恰有 $\sum C_j$ 个馒头可装时花费 $\sum E_j$ 的最小值（因为卖出的最大值已经确定了）

这是一个典型的背包模型

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, inf = 0x3f3f3f3f;
int m, n;
int p[N], d[N];
int ans;
int dp[N];
struct Node {
    int c, e;
} e[505];
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++) scanf("%d", &p[i]), d[i] = d[i - 1] + p[i], dp[i] = inf;
    sort(p + 1, p + 1 + m, greater<int>());
    for (int i = 1; i <= m; i++) d[i] = d[i - 1] + p[i];
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &e[i].c, &e[i].e);
        for (int j = m; j >= 0; j--) {
            dp[j] = min(dp[j], dp[max(0, j - e[i].c)] + e[i].e);
        }
    }
    for (int i = 0; i <= m; i++) ans = max(ans, d[i] - dp[i]);
    printf("%d", ans);
    return 0;
}

注意

1. 注意转移的时候方程应该是 $dp(j) = \min {dp(j), dp(j - C)}$，但有可能 $j < C$ 从而访问负数下标，因此是 $dp(j) = \min \{ dp(j), dp(\max \{ 0,j - C \}) \}$ 从实际意义来谈，也不可能选取负数个馒头
2. 求最小值初始化为最大值