programmer330 @ 2024-10-23 10:13:35
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 105
vector<int>v[65],w[65];
vector<int>v1[65],w1[65];
int f[320005];
void dfs(int i,int j,int price,int val){
if(j==v[i].size()){
v1[i].push_back(price+v[i][0]);
w1[i].push_back(val+v[i][0]*w[i][0]);
return;
}
dfs(i,j+1,price,val);
dfs(i,j+1,price+v[i][j],val+v[i][j]*w[i][j]);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int price,p,q;
cin>>price>>p>>q;
if(q==0){
v[i].push_back(price);
w[i].push_back(p);
}else{
v[q].push_back(price);
w[q].push_back(p);
}
}
for(int i=1;i<=m;i++){
if(v[i].size()==0)continue;
else dfs(i,1,0,0);
}
memset(f,0xcf,sizeof(f));
f[0]=0;
for(int i=1;i<=m;i++){
if(v[i].size()==0)continue;
for(int j=n;j>=0;j--){
for(int k=0;k<v1[i].size();k++){
if(j>=v1[i][k]){
f[j]=max(f[j],f[j-v1[i][k]]+w1[i][k]);
}
}
}
}
int ans=0;
for(int j=0;j<=n;j++)ans=max(ans,f[j]);
cout<<ans<<endl;
return 0;
}by songyuteng123 @ 2024-12-05 16:41:10
#include<bits/stdc++.h>
using namespace std;
const int N=35000;
int dp[N];
int n,m;
int maxn;
struct node{
int zv,zp,fv1,fp1,fv2,fp2;
};
node a[100];
int main(){
cin>>maxn>>n;
int v,p,q;
for(int i=1;i<=n;i++){
cin>>v>>p>>q;
if(q==0){
a[i].zv=v;
a[i].zp=v*p;
}
else{
if(a[q].fp1==0){
a[q].fv1=v;
a[q].fp1=v*p;
}
else{
a[q].fv2=v;
a[q].fp2=v*p;
}
}
}
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)
dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv1]+a[i].zp+a[i].fp1);
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].fp2);
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].fp1+a[i].fp2);
}
}
cout<<dp[maxn];
return 0;
}