记录编号	393077	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	皓芷	是否通过	通过
代码语言	C++	运行时间	0.355 s
提交时间	2017-04-09 21:08:05	内存使用	35.22 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,w[61],v[61],fa[61],z,f[61][150001];
vector<int>son[61];
void backpack_01(int a)
{
	for(int i=0;i<son[a].size();i++)
	  for(int k=n-w[a];k>=w[son[a][i]];k--)
	    if(f[a][k]<f[a][k-w[son[a][i]]]+v[son[a][i]])//{
	      f[a][k]=f[a][k-w[son[a][i]]]+v[son[a][i]];//printf("---%d %d %d\n",a,k,f[a][k]);}
}
int main()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	scanf("%d%d",&n,&m);
	n/=10;
	for(int i=1;i<=m;i++)
	{
	  scanf("%d%d%d",&w[i],&v[i],&fa[i]);
	  son[fa[i]].push_back(i);
	  w[i]/=10;
	  v[i]*=w[i];
	}
	for(int i=1;i<=m;i++)
	  if(!son[i].empty())
	    backpack_01(i);
	    int cvb=0;
	for(int i=1;i<=m;i++)if(fa[i]==0)
	  for(int j=n;j>=w[i];j--)
	    for(int k=0;k<=j-w[i];k++)//{
	      if(f[0][j]<f[0][j-k-w[i]]+f[i][k]+v[i])
	        f[0][j]=f[0][j-k-w[i]]+f[i][k]+v[i];
			//printf("---%d %d %d\n",cvb++,j,f[0][j]);}
	printf("%d",f[0][n]*10);
	return 0;
}