1 条题解
-
0
每处理一组时倒序容量,确保同组最多选一件;使用 long long 保存总价值。
#include <bits/stdc++.h> using namespace std; int main(){int cap,n,groups;cin>>cap>>n>>groups;vector<vector<pair<int,long long>>>a(groups+1);while(n--){int w,g;long long value;cin>>w>>value>>g;a[g].push_back({w,value});}vector<long long>d(cap+1);for(auto&group:a)for(int j=cap;j>=0;j--)for(auto[w,value]:group)if(w<=j)d[j]=max(d[j],d[j-w]+value);cout<<d[cap]<<"\n";}
- 1
信息
- ID
- 3947
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者