全WA求助

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

LiaoYF @ 2023-02-17 20:51:37

#include<iostream>
#include<vector>
using namespace std;
int n,m,v[105],p[105],q[105],f[100005];
vector<int> fj[105];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>p[i]>>q[i];
        p[i]*=v[i];
        if(q[i]!=0)fj[q[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+p[i]);
            if(fj[i].size()==1){
                if(j-v[i]>=v[fj[i][0]]){
                    f[j]=max(f[j],f[j-v[i]-v[fj[i][0]]]+p[i]+p[fj[i][0]]);
                }
            }else if(fj[i].size()==2){
                if(j-v[i]>=v[fj[i][0]]){
                    f[j]=max(f[j],f[j-v[i]-v[fj[i][0]]]+p[i]+p[fj[i][0]]);
                }
                if(j-v[i]>=v[fj[i][1]]){
                    f[j]=max(f[j],f[j-v[i]-v[fj[i][1]]]+p[i]+p[fj[i][1]]);
                }
                if(j-v[i]-v[fj[i][0]]>=v[fj[i][1]]){
                    f[j]=max(f[j],f[j-v[i]-v[fj[i][0]]-v[fj[i][1]]]+p[i]+p[fj[i][0]]+p[fj[i][1]]);
                }
            }
        }
    }
    cout<<f[m];
    return 0;
}

n和m与题目中的是反的


|