求助

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

yuangq @ 2018-10-03 11:22:00

#include<iostream>
#include<vector>
#include<cstring>
#define LL long long
#define MAXN 65
#define MAXC 3205
using namespace std;

//int a[MAXN];
int C,N;
struct Node
{
    int v,p;
    Node(int v=0,int p=0):v(v),p(p){}
} nList[MAXN];

vector<Node> Adj[MAXN]; 
LL dp[MAXC];
LL temp[4][MAXC];

int main()
{
    //freopen("train.in","r",stdin);
    //freopen("train.out","w",stdout);
    cin>>C>>N;
    int v,p,q;
    for(int i=1;i<=N;i++)
    {
        cin>>v>>p>>q;
        v/=10;
        if(q==0)
        {
            nList[i]=Node(v,p);
        }
        else
        {
            Adj[q].push_back(Node(v,p));
        }
    }

    for(int i=1;i<=N;i++)
    {
        if(nList[i].p==0)
        {
            continue;
        } 
        memset(temp,0,sizeof(temp));
        int v0=nList[i].v;
        int p0=nList[i].p;
        for(int j=C;j>=1;j--)
        {
            if(j-v0>=0)
            {
                temp[0][j]=max(temp[0][j],dp[j-v0]+v0*p0);
            }
        }
        if(Adj[i].size()>0)
        {
            int v1=Adj[i][0].v;
            int p1=Adj[i][0].p;
            for(int j=C;j>=1;j--)
            {
                if(j-v0-v1>=0)
                {
                    temp[1][j]=max(temp[1][j],dp[j-v0-v1]+v0*p0+v1*p1);
                }
            }

            if(Adj[i].size()>1)
            {
                int v2=Adj[i][1].v; 
                int p2=Adj[i][1].p;

                for(int j=C;j>=1;j--)
                {
                    if(j-v0-v2>=0)
                    {
                        temp[2][j]=max(temp[2][j],dp[j-v0-v2]+v0*p0+v2*p2);
                    }
                } 

                for(int j=C;j>=1;j--)
                {
                    if(j-v0-v1-v2>=0)
                    {
                        temp[3][j]=max(temp[3][j],dp[j-v0-v1-v2]+v0*p0+v1*p1+v2*p2);
                    }
                } 
            }
        }
    }
    LL ans=0;
    for(int j=1;j<=C;j++)
    {
        ans=max(ans,dp[j]);
    }
    cout<<ans*10;
    return 0;
}

|