求助!!!

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

htomo111 @ 2022-11-20 20:55:08

感觉没问题啊???

样例过了只得10pts

#include<iostream>
using namespace std;
struct node
{
    int lkid,rkid;
    bool fl=true;
}s[35000];
int n,f[35000],w[35000],v[35000],h;
int main()
{
    cin>>n>>h;
    for(int i=1;i<=h;i++)
    {
        int a;
        cin>>w[i]>>v[i]>>a;
        v[i]*=w[i];
        if(a!=0)
        {
            if(s[a].lkid>0)s[a].rkid=i;
            else s[a].lkid=i;
            s[i].fl=false;
        }
    }
    for(int i=1;i<=h;i++)
    {
        if(s[i].fl==false)continue;
        for(int j=n;j>=w[i];j--)
        {
            if(j>=w[i])f[j]=max(f[j],f[j-w[i]]+v[i]);
            if(j>=w[i]+w[s[i].lkid])f[j]=max(f[j],f[j-w[i]-w[s[i].lkid]]+v[i]+v[s[i].lkid]);
            if(j>=w[i]+w[s[i].rkid])f[j]=max(f[j],f[j-w[i]-w[s[i].rkid]]+v[i]+v[s[i].rkid]);
            if(j>=w[i]+w[s[i].lkid]+w[s[i].rkid])f[j]=max(f[j],f[j-w[i]-w[s[i].lkid]]+v[i]+v[s[i].lkid]+v[s[i].rkid]);
        }
    }
    cout<<f[n];
    return 0;
}

|