记录编号	242769	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2016-03-28 14:48:30	内存使用	0.42 MiB

#include<cstdio>
const int maxn=100;
int w[maxn],v[maxn],fu[maxn][3];
bool zhu[maxn];
int _w[100][10],_v[100][10];
int num[maxn];
int f[32005];
int max(int a,int b){
	return a>b?a:b;
}
int main(){
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	int money,n;
	scanf("%d %d",&money,&n);
	int tmp;
	for(int i=1;i<=n;++i){
		scanf("%d %d %d",&w[i],&v[i],&tmp);
		v[i]*=w[i];
		if(tmp)fu[tmp][++fu[tmp][0]]=i;
		else zhu[i]=true;
	}
	int len=0,k;
	for(int i=1;i<=n;++i){
		if(zhu[i]){
			_w[++len][1]=w[i];
			_v[len][1]=v[i];
			num[len]=1;
			if(fu[i][0]>=1){
				_w[len][2]=w[fu[i][1]]+w[i];
				_v[len][2]=v[fu[i][1]]+v[i];
				num[len]=2;
			}
			if(fu[i][0]==2){
				_w[len][3]=w[fu[i][2]]+w[i];
				_v[len][3]=v[fu[i][2]]+v[i];
				_w[len][4]=w[fu[i][2]]+w[fu[i][1]]+w[i];
				_v[len][4]=v[fu[i][2]]+v[fu[i][1]]+v[i];
				num[len]=4;
			}
		}
	}
	for(int i=1;i<=len;++i){
		for(int j=money;j>=0;--j){
			for(int k=1;k<=num[i];++k){
				if(j-_w[i][k]>=0)f[j]=max(f[j],f[j-_w[i][k]]+_v[i][k]);
			}
		}
	}
	printf("%d\n",f[money]);
	fclose(stdin);fclose(stdout);
	return 0;
}