题解（个人认为代码可读性较高
2025-04-26 14:30:34
发布于：浙江
55阅读
0回复
0点赞
P1064 题解报告
题目链接
首先我们针对于每一件物品我们定义其 价值 为 。
其次针对于每一组物品，我们有以下五种选择：
1. 只买主件
2. 买主机加附件 1
3. 买主件加附件 2
4. 全买
5. 都不买
以上五种选择对应的代价和价值是（此处我们令当前这组主件为 ，附件 1 为 ，附件 2 为 ）：
| 编号 | 购买情况 | 代价 | 价值 |
|---|---|---|---|
| 1 | 只买主件 | ||
| 2 | 买主机加附件 1 | ||
| 3 | 买主件加附件 2 | ||
| 4 | 全买 | ||
| 5 | 都不买 |
然后考虑存储问题，不妨定义一个二维数组 ，其中第一维度存储主件，第二维度存储附件。
其中第 维度下标为 的元素表示第 个物品的第 个附件，同理，第 维度下标为 的元素表示第 个物品的第 个附件，特别地，为了存储每个主件分别有多少个附件，我们定义第 维度下标为 的元素 表示第 个物品有 个附件（显然，如果第 个物品为附件，那么 一定为 ），且所有主件均属于编号为 的物品的附件。
为了方便理解，接下来我们用样例来举例二维数组 的存储情况。
| 表头 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | ||||
| 1 | 空 | |||
| 2 | 空 | 空 | 空 | |
| 3 | 空 | 空 | 空 | |
| 4 | 空 | 空 | 空 | |
| 5 | 空 | 空 | 空 |
见上， 表示一共有 个主件， 表示第 个物品一共有 个附件，其中第 个附件（即 ）是编号为 的物品。
最后我们只需将每组看做一个物品跑个采药（即 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;
}
全部评论 4
贴一下我写的代码qwq
#include<bits/stdc++.h> #define int long long using namespace std; struct node{ int w,v,idx,f; // w价格 v价值 idx分组 f是否为主件 }; signed main(){ int n,m; cin>>n>>m; vector<node> a(m+1); for(int i=1;i<=m;i++){ int v,p,q; cin>>v>>p>>q; if(q == 0){ a[i].idx = i; a[i].f = 0; a[i].v = v*p; a[i].w = v; }else{ a[i].idx = q; a[i].f = 1; a[i].v = v*p; a[i].w = v; } }; sort(a.begin()+1,a.end(),[](node a,node b){ if(a.idx == b.idx) return a.f < b.f; return a.idx < b.idx; }); vector<int> dp(n+1); for(int i=1;i<=m;i++){ if(a[i].f) continue; for(int j=n;j>=a[i].w;j--){ // 策略1 只买主件(01板) dp[j] = max(dp[j],dp[j-a[i].w]+a[i].v); // 策略2 买第一个附件 if( i+1 <= m && // 防止越界 a[i+1].idx == a[i].idx && // 下一个是附件 j >= a[i].w+a[i+1].w // 买得起 ){ dp[j] = max(dp[j], dp[j - a[i].w - a[i+1].w] + a[i].v + a[i+1].v); } // 策略3 买第二个附件 if( i+2 <= m && // 防止越界 a[i+2].idx == a[i].idx && // 下下一个是附件 j >= a[i].w+a[i+2].w // 买得起 ){ dp[j] = max(dp[j], dp[j - a[i].w - a[i+2].w] + a[i].v + a[i+2].v); } // 策略4 两个附件都买 if( a[i+1].idx == a[i].idx && // 下一个是附件 a[i+2].idx == a[i].idx && // 下下一个是附件 j >= a[i].w+a[i+1].w+a[i+2].w // 买得起 ){ dp[j] = max(dp[j], dp[j - a[i].w - a[i+1].w - a[i+2].w] + a[i].v + a[i+1].v + a[i+2].v); } } } cout<<dp[n]; return 0; }2026-07-27 来自 辽宁
0
有帮助，赞一个