Re_myailun @ 2023-09-21 19:59:11
#include<bits/stdc++.h>
using namespace std;
int m,n;
struct node{
long long v;
long long p;
long long q;
long long j;
}a[33333];
long long f[33333];
bool flag[60][32000];//记录每种转态那些物品是被买过的
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a[i].v>>a[i].p>>a[i].q;
//输入价格,重要度,对应的主件
}
for(int i=1;i<=n;i++){
a[i].j=a[i].v*a[i].p;
}//每个物品的价值
for(int i=1;i<=n;i++){//物品数
for(int j=m;j>=a[i].v;j--){
if(a[i].q!=0&&j-a[i].v-a[a[i].q].v>=0&&!flag[a[i].q][j-a[i].v-a[a[i].q].v]){//当前需要买主件,并且逐渐没买
f[j]=max(f[j],f[j-a[i].v-a[a[i].q].v]+a[i].j+a[a[i].q].j);
flag[a[i].q][j]=1;
}else if(a[i].q==0){
f[j]=max(f[j],f[j-a[i].v]+a[i].j);//不需要买主件
}else if(a[i].q!=0&&flag[a[i].q][j-a[i].v]){//需要主件,并且买过了
f[j]=max(f[j],f[j-a[i].v]+a[i].j);
}
}
}
cout<<f[m];
}