记录编号	522177	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	Ceres	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2018-11-09 18:20:46	内存使用	2.09 MiB

#include <cstdio>
#define MAX 32000
#define max(a,b) a>b?a:b
using namespace std;
int n,m;
int f[MAX+10],num;
struct node
{
    int v,p,q;
    int lk,rk;
    void init()
    {
        v=p=lk=rk=0;
    }
}th[70];
int main()
{
    freopen("budget.in","r",stdin);
    freopen("budget.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        th[i].init();
        scanf("%d%d%d",&th[i].v,&th[i].p,&th[i].q);
        th[i].p*=th[i].v;
        if(th[i].q)
            if(!th[th[i].q].lk)
                th[th[i].q].lk=i;
            else
                th[th[i].q].rk=i;
    }
    for(int i=1;i<=m;i++)
        if(!th[i].q)
            for(int j=n;j>=th[i].v;j--)
            {
                f[j]=max(f[j],f[j-th[i].v]+th[i].p);
                if(th[i].lk && th[i].v+th[th[i].lk].v<=j)
                {
                    f[j]=max(f[j],f[j-(th[i].v+th[th[i].lk].v)]+th[i].p+th[th[i].lk].p);
                    if(th[i].rk && th[i].v+th[th[i].lk].v+th[th[i].rk].v<=j)
                        f[j]=max(f[j],f[j-(th[i].v+th[th[i].lk].v+th[th[i].rk].v)]+th[i].p+th[th[i].lk].p+th[th[i].rk].p);
                }
                if(th[i].lk && th[i].v+th[th[i].rk].v<=j)
                    f[j]=max(f[j],f[j-(th[i].v+th[th[i].rk].v)]+th[i].p+th[th[i].rk].p);
            }
    printf("%d\n",f[n]);
    return 0;
}