weichen123 @ 2022-10-06 18:42:04
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<string>
#include<stack>
#include<queue>
using namespace std;
struct node{
int zv,zp;
int fv1,wv1;
int fv2,wv2;
};
node a[35000];
int maxn,n;
int vi,pi,qi;
int dp[35000];
int main(){
cin>>maxn>>n;
for(int i=1;i<=n;i++){
cin>>vi>>pi>>qi;
if(qi==0){
a[i].zv=vi;
a[i].zp=vi*pi;
}
else{
if(a[qi].wv1==0){
a[qi].fv1=vi;
a[qi].wv1=vi*pi;
}
else{
a[qi].fv2=vi;
a[qi].wv2=vi*pi;
}
}
}
for(int i=1;i<=n;i++){
if(a[i].zp==0) continue;
for(int j=maxn;j>=a[i].zv;j--){
dp[j]=max(dp[j],dp[j-a[i].zv]+a[i].zp);
if(a[i].zv+a[i].fv1<=j) //在a[i].zp卡
dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv1]+a[i].zp+a[i]+wv1);
if(a[i].zv+a[i].fv2<=j)
dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv2]+a[i].zp+a[i]+wv2);
if(a[i].zv+a[i].fv1+a[i].fv2<=j)
dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv1-a[i].fv2]+a[i].zp+a[i]+wv1+a[i].wv2);
}
}
cout<<dp[n];
return 0;
}
by Sprague_Garundy @ 2022-10-06 18:43:29
@weichen123 你 .
写成 +
了。
by DeepWinter @ 2022-10-06 18:44:04
@weichen123 是a[i].wv1/wv2吧
by weichen123 @ 2022-10-06 18:49:39
@Sprague_Garundy thank 看了一下午 靠
by weichen123 @ 2022-10-06 18:51:02
@frank804 DL,不是哟。
by weichen123 @ 2022-10-06 18:52:56
@frank804 就是列举各种情况,减去价钱,加上价值
by DeepWinter @ 2022-10-06 18:54:18
@weichen123 我指的是a[i].wv1或a[i].wv2,你写成+了
by weichen123 @ 2022-10-06 18:55:44
@frank804 我误会了 thank了