救救孩子。。。。

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

阿沐 @ 2019-07-24 21:04:40

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,m,v,p,q,c[32001],t,l;
ll f[32001],b[32001];
struct ttp{
    ll v;
    ll w;
    ll q;
}a[61][5];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v>>p>>q;

        if(!q)
        {

             b[i]=i;
            a[i][0].v=v;
            a[i][0].w=v*p;
        //  a[b[i]][0].q=q;

        }
        else 
        {    
           b[i]=q;
           if(c[q]==0) c[q]++;
            c[q]++;
            a[b[i]][c[q]].v=v;
            a[b[i]][c[q]].w=v*p;

        }
    }
    for(int i=1;i<=m;i++)
    for(int j=n;j>=a[i][0].v;j--)
    {
        if(a[i][0].v==0) continue;

            if(a[b[i]][0].v)
            {
                t=a[b[i]][0].v;
                l=a[b[i]][0].w;
                if(j>=t)
                f[j]=max(f[j],f[j-t]+l);
            }
            if(a[b[i]][1].v)
            {
                t=a[b[i]][0].v+a[b[i]][1].v;
                l=a[b[i]][0].w+a[b[i]][1].w;
                if(j>=t)
                f[j]=max(f[j],f[j-t]+l);
            }
            if(a[b[i]][2].v)
            {
                t=a[b[i]][0].v+a[b[i]][2].v;
                l=a[b[i]][0].w+a[b[i]][2].w;
                if(j>=t)
                f[j]=max(f[j],f[j-t]+l);

            }
           if(a[b[i]][1].v&&a[b[i]][2].v)
           {
                t=a[b[i]][0].v+a[b[i]][1].v+a[b[i]][2].v;
                l=a[b[i]][0].w+a[b[i]][1].w+a[b[i]][2].w;
                if(j>=t)
                f[j]=max(f[j],f[j-t]+l);
           }

    }
    cout<<f[n];
    return 0;
}

|