90pts求调
查看原帖
90pts求调
1486095
sunnybear楼主2025/1/17 21:02
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int zv,zp,fv1,fp1,fv2,fp2;
}a[100];
int maxn,n;
int v,p,q;
int dp[35000];
signed main(){
    cin>>maxn>>n;
    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].fp1);
            if(a[i].zv+a[i].fv2<=j) dp[j]=max(dp[j],dp[j-a[i].zv-a[i].fv2]+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;
}

用的是结构体 依赖性背包实在看不出问题

2025/1/17 21:02
加载中...