蒟蒻求助

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

doctorZ_ @ 2019-02-21 12:40:43

#include<iostream>
#include<cstdio>
#define N 6000
using namespace std;
int v[N+1],w[N+1],f[33000];
int mt[N+1][3];
bool judge[N+1];
int main()
{
    int n,m;
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int p,q;
        scanf("%d %d %d",&w[i],&p,&q);
        v[i]=p*w[i];
        if(q!=0)
        {
            if(mt[q][1]==0)
                mt[q][1]=i;
            else
                mt[q][2]=i;
        }
        else
            judge[i]=true;
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            if(judge[i]==true)
            {
                int z=i,f1=mt[i][1],f2=mt[i][2];
                if(j>=w[z])
                    f[j]=max(f[j],f[j-w[z]]+v[z]);
                if(j>=w[z]+w[f1])
                    f[j]=max(f[j],f[j-w[z]-w[f1]]+v[z]+v[f1]);
                if(j>=w[z]+w[f2])
                    f[j]=max(f[j],f[j-w[z]-w[f1]]+v[z]+v[f1]);
                if(j>=w[z]+w[f1]+w[f2])
                    f[j]=max(f[j],f[j-w[z]-w[f1]-w[f2]]+v[z]+v[f1]+v[f2]);
            }
    printf("%d",f[m]);
    return 0;
}

|