LiaoYF @ 2023-02-17 20:51:37
#include<iostream>
#include<vector>
using namespace std;
int n,m,v[105],p[105],q[105],f[100005];
vector<int> fj[105];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>v[i]>>p[i]>>q[i];
p[i]*=v[i];
if(q[i]!=0)fj[q[i]].push_back(i);
}
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+p[i]);
if(fj[i].size()==1){
if(j-v[i]>=v[fj[i][0]]){
f[j]=max(f[j],f[j-v[i]-v[fj[i][0]]]+p[i]+p[fj[i][0]]);
}
}else if(fj[i].size()==2){
if(j-v[i]>=v[fj[i][0]]){
f[j]=max(f[j],f[j-v[i]-v[fj[i][0]]]+p[i]+p[fj[i][0]]);
}
if(j-v[i]>=v[fj[i][1]]){
f[j]=max(f[j],f[j-v[i]-v[fj[i][1]]]+p[i]+p[fj[i][1]]);
}
if(j-v[i]-v[fj[i][0]]>=v[fj[i][1]]){
f[j]=max(f[j],f[j-v[i]-v[fj[i][0]]-v[fj[i][1]]]+p[i]+p[fj[i][0]]+p[fj[i][1]]);
}
}
}
}
cout<<f[m];
return 0;
}
n和m与题目中的是反的