lsz0205 @ 2022-11-14 20:08:26
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
// 首先为每个主件建立一个组
// 其次,把对应的附件添加进组
vector<int> v[70];
vector<int> w[70];
vector<int> fv;
vector<int> fw;
vector<int> od;
int n,m;
int f[70][32000+10];
vector<int> nv[70];
vector<int> nw[70];
int main(){
for(int i=0;i<70;i++) v[i].push_back(0),w[i].push_back(0);
cin>>m>>n;
int idx=1;
for(int i=1;i<=n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z==0){
v[idx].push_back(x);
w[idx].push_back(x*y);
idx++;
}else{ // 附件
fv.push_back(x);
fw.push_back(x*y);
od.push_back(z);
}
}
// 把各个附件添加进组
for(int i=0;i<od.size();i++){
int no=od[i];
v[no].push_back(fv[i]);
w[no].push_back(fw[i]);
}
// 计算真正的组内的元素的v和w
for(int i=1;i<=idx-1;i++){ // 一共有idx-1个组
nv[i].push_back(0);
nw[i].push_back(0);
if(v[i].size()==2){ // 只有主件
nv[i].push_back(v[i][1]);
nw[i].push_back(w[i][1]);
}else if(v[i].size()==3){ // 一个主件一个附件
nv[i].push_back(v[i][1]);
nw[i].push_back(w[i][1]);
nv[i].push_back(v[i][1]+v[i][2]);
nw[i].push_back(w[i][1]+w[i][2]);
}else{ // 一个主件两个附件
nv[i].push_back(v[i][1]);
nw[i].push_back(w[i][1]);
nv[i].push_back(v[i][1]+v[i][2]);
nw[i].push_back(w[i][1]+w[i][2]);
nv[i].push_back(v[i][1]+v[i][3]);
nw[i].push_back(w[i][1]+w[i][3]);
nv[i].push_back(v[i][1]+v[i][2]+v[i][3]);
nw[i].push_back(w[i][1]+w[i][2]+w[i][3]);
}
}
for(int i=1;i<=idx-1;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j];
for(int k=1;k<nv[i].size();k++){
if(j>=nv[i][k]) f[i][j]=max(f[i][j],f[i-1][j-nv[i][k]]+nw[i][k]);
}
}
}
cout<<f[idx-1][m]<<endl;
return 0;
}
by ZJH123767 @ 2022-11-16 07:55:33
看起来挺对
by PCCP @ 2022-11-17 20:40:07
可以看看我在本题发的我的帖子,对你会很有启发
by lsz0205 @ 2022-11-19 19:20:22
@PCCP 十分感谢