Grace25 @ 2020-11-01 12:46:28
X﹏X,我真的太弱了
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,s,m=1,dp[32010],dp_f[32010];
struct thing{
int v,w,h;
}main_item[10010],annex_item[1010][1010];
int main(){
int v,w,h;
cin >> s >> n;
for(int i=1;i<=n;i++){
cin >> w >> v >> h;
if (!h){//是主件
main_item[0].h++;//件数加一
main_item[main_item[0].h].v = v*w//储存
main_item[main_item[0].h].w = w;
}else{//是附件
annex_item[h][0].h++;//件数加一
annex_item[h][annex_item[h][0].h].v = v*w;//储存
annex_item[h][annex_item[h][0].h].w = w;
}
}
for(int i=1;i<=main_item[0].h;i++){
memcpy(dp_f,dp,sizeof(dp));
for(int j=1;j<=annex_item[i][0].h;j++){//对附件进行0-1背包
w=annex_item[i][j].w;
v=annex_item[i][j].v;
for(int x=s;x>=w;x--){
dp_f[x]=max(dp_f[x],dp_f[x-w]+v);
}
}
w=main_item[i].w;
v=main_item[i].v;
for(int j=s;j>=w;j--){
dp[j]=max(dp[j],dp_f[j-w]+v);
}
}
cout << dp[s];
return 0;
}