yggdyy_ @ 2020-09-17 22:27:41
#include <bits/stdc++.h>
using namespace std;
int v[100],w[100],p[100];
int dp[320101];
int n,m;
int pl[100][3][3],p_cnt[100];
//pl[i][j][1]表示第i个物品的第j个附件的价值,pl[i][j][2]表示花费
//p_cnt[i]表示第i个物品有几个附件
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>w[i]>>v[i]>>p[i];v[i]*=w[i];
if(p[i]>0){
p_cnt[p[i]]++;
pl[p[i]][p_cnt[p[i]]][1]=v[i];
pl[p[i]][p_cnt[p[i]]][2]=w[i];
}
}
for(int i=1;i<=m;i++){
if(p[i]!=0)continue;
if(p_cnt[i]==0){
for(int j=n;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}else if(p_cnt[i]==1){
for(int j=n;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
for(int j=n;j>=w[i]+pl[i][1][2];j--)dp[j]=max(dp[j],dp[j-w[i]-pl[i][1][2]]+v[i]+pl[i][1][1]);
}else{
for(int j=n;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
for(int j=n;j>=w[i]+pl[i][1][2];j--)dp[j]=max(dp[j],dp[j-w[i]-pl[i][1][2]]+v[i]+pl[i][1][1]);
for(int j=n;j>=w[i]+pl[i][2][2];j--)dp[j]=max(dp[j],dp[j-w[i]-pl[i][2][2]]+v[i]+pl[i][2][1]);
for(int j=n;j>=w[i]+pl[i][1][2]+pl[i][2][2];j--)dp[j]=max(dp[j],dp[j-w[i]-pl[i][1][2]-pl[i][2][2]]+v[i]+pl[i][1][1]+pl[i][2][1]);
}
}cout<<dp[n];
return 0;
}
by lion0514 @ 2020-10-18 20:18:04
正经的标题又减少了