记录编号	445918	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	REALIZE_BEYOND	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-09-07 07:54:23	内存使用	0.44 MiB

#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>

using namespace std;
int n,m,v[65],f[32005],w[65],q,cur=0,fa[65];
vector <int> a[65];
int main(){
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	cin>>n>>m;
	n/=10;
	for(int i=1;i<=m;i++){
		cin>>v[i]>>w[i]>>q;
		v[i]/=10;
		w[i]*=v[i];
		if(q) a[q].push_back(i);
		else fa[++cur]=i;
	}
	for(int o=1;o<=cur;o++){
		int i=fa[o];
		for(int j=n;j>=v[i];j--){
			f[j]=max(f[j],f[j-v[i]]+w[i]);
			for(int k=0;k<a[i].size();k++)
				if(j>=v[i]+v[a[i][k]])
				  f[j]=max(f[j],f[j-(v[i]+v[a[i][k]])]+w[i]+w[a[i][k]]);
			if(a[i].size()==2&&v[i]+v[a[i][0]]+v[a[i][1]]<=j)
			  f[j]=max(f[j],f[j-(v[i]+v[a[i][0]]+v[a[i][1]])]+w[i]+w[a[i][0]]+w[a[i][1]]);
		}
	}
	cout<<f[n]*10;
	return 0;
}