P1064 题解报告

题目链接
首先我们针对于每一件物品我们定义其 价值 为 $c_i=w_i \times v_i$。
其次针对于每一组物品，我们有以下五种选择：
1. 只买主件
2. 买主机加附件 1
3. 买主件加附件 2
4. 全买
5. 都不买
以上五种选择对应的代价和价值是（此处我们令当前这组主件为 $mc$，附件 1 为 $c_1$，附件 2 为 $c_2$）：

编号	购买情况	代价	价值
1	只买主件	$v_{mc}$	$w_{mc}$
2	买主机加附件 1	$v_{mc}+v_{c_1}$	$w_{mc}+w_{c_1}$
3	买主件加附件 2	$v_{mc}+v_{c_2}$	$w_{mc}+w_{c_2}$
4	全买	$v_{mc}+v_{c_1}+v_{c_2}$	$w_{mc}+w_{c_1}+w_{c_2}$
5	都不买	$0$	$0$

然后考虑存储问题，不妨定义一个二维数组 $c$，其中第一维度存储主件，第二维度存储附件。
其中第 $i$ 维度下标为 $1$ 的元素表示第 $i$ 个物品的第 $1$ 个附件，同理，第 $i$ 维度下标为 $2$ 的元素表示第 $i$ 个物品的第 $2$ 个附件，特别地，为了存储每个主件分别有多少个附件，我们定义第 $i$ 维度下标为 $0$ 的元素 $c_{i,0}$ 表示第 $i$ 个物品有 $c_{i,0}$ 个附件（显然，如果第 $i$ 个物品为附件，那么 $c_{i,0}$ 一定为 $0$），且所有主件均属于编号为 $0$ 的物品的附件。
为了方便理解，接下来我们用样例来举例二维数组 $c$ 的存储情况。

表头	0	1	2	3
0	$3$	$1$	$4$	$5$
1	$2$	$2$	$3$	空
2	$0$	空	空	空
3	$0$	空	空	空
4	$0$	空	空	空
5	$0$	空	空	空

见上，$c_{0,0}$ 表示一共有 $3$ 个主件，$c_{1,0}$ 表示第 $1$ 个物品一共有 $2$ 个附件，其中第 $2$ 个附件（即 $c_{1,2}$）是编号为 $3$ 的物品。

---

最后我们只需将每组看做一个物品跑个采药（即 P1048）即可：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, f[32001], c[32001][61];
int v[32001], w[32001];
int update(int i, int k) { //update意为更新
	int tmp = f[k], mc = c[0][i], c1 = c[mc][1], c2 = c[mc][2]; //mc是main component（主件）
	int vmc = v[mc], v1 = v[c1], v2 = v[c2];
	//!!!重要部分--状态转移方程
	//上面讲的五种情况，第五种情况就是f[k]，所以直接放第7行上了（tmp初始化） 
	if (k - vmc >= 0) tmp = max(f[k - vmc] + w[mc], tmp);
	if (k - vmc - v1 >= 0) tmp = max(f[k - vmc - v1] + w[mc] + w[c1], tmp);
	if (k - vmc - v2 >= 0) tmp = max(f[k - vmc - v2] + w[mc] + w[c2], tmp);
	if (k - vmc - v1 - v2 >= 0) tmp = max(f[k - vmc - v1 - v2] + w[mc] + w[c1] + w[c2], tmp);
	//
	return tmp;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int q;
		cin >> v[i] >> w[i], w[i] *= v[i]; //见文末给出的链接(开心的金明 题解，里面有详讲)，此处主要是对价值重新定义了一遍 
		cin >> q, c[q][++c[q][0]] = i; //添加附件
	}
	for (int i = 1; i <= c[0][0]; i++) for (int k = n; k >= v[i]; k--) f[k] = update(i, k); //01背包模板（除了状态转移不同）
	cout << f[n];
	return 0;
}

推销同类题