记录编号	115428	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	任杰	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2014-08-19 16:33:44	内存使用	5.78 MiB

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define MAX_N 30001
#define MAX_M 60

int N,m;
int v[MAX_M],w[MAX_M],relyon[MAX_M];
int attachcnt[MAX_M];
int attach[MAX_M][MAX_M];
int dp[MAX_N];
int nv[70][10000],nw[70][10000];
int ncnt;
int mcnt[70];

void dfs(int cur,int f,int vt,int wt)
{
	if(attachcnt[f]==0)
	{
		nv[ncnt][mcnt[ncnt]]=v[f];
		nw[ncnt][mcnt[ncnt]]=v[f]*w[f];
		mcnt[ncnt]++;
		return;
	}
	if(cur==attachcnt[f])
	{
		nv[ncnt][mcnt[ncnt]]=vt;
		nw[ncnt][mcnt[ncnt]]=wt;
		mcnt[ncnt]++;
		return;
	}

	int id=attach[f][cur];
	dfs(cur+1,f,vt,wt);
	dfs(cur+1,f,vt+v[id],wt+v[id]*w[id]);
}

int main()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);

	cin>>N>>m;

	for(int i=0;i<m;i++)
	{
		cin>>v[i]>>w[i]>>relyon[i];

		if(relyon[i])
		{
			int &t=attachcnt[relyon[i]-1];
			attach[relyon[i]-1][t]=i;
			t++;
		}
	}

	ncnt=0;
	for(int i=0;i<m;i++)
	{
		if(!relyon[i])
		{
			dfs(0,i,v[i],w[i]*v[i]);
			ncnt++;
		}
	}

	for(int i=1;i<=ncnt;i++)
	{
		for(int j=N;j>=0;j--)
		{
			for(int k=0;k<mcnt[i-1];k++)
			{
				if(j>=nv[i-1][k])
					dp[j]=max(dp[j],dp[j-nv[i-1][k]]+nw[i-1][k]);
			}
		}
	}

	cout<<dp[N]<<endl;

	return 0;
}