大佬50分求助

P1064 [NOIP2006 提高组] 金明的预算方案

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];
}

|