记录编号	470567	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	liuyu	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-11-04 22:05:46	内存使用	0.44 MiB

#include<bits/stdc++.h>
using namespace std;

int m,n;
int w[70][6],v[70][6],o[70];
int x[70],y[70];
int f[32009];
vector<int>vec[70];

void init(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		if(c==0)o[i]=1;
		else vec[c].push_back(i);
		x[i]=a,y[i]=b;
	}
	for(int i=1;i<=n;i++){
		if(o[i]){
			w[i][0]=x[i],v[i][0]=x[i]*y[i];
		}
		if(vec[i].size()){
			int a=vec[i][0];
			w[i][1]=x[i]+x[a];
			v[i][1]=v[i][0]+x[a]*y[a];
		}
		if(vec[i].size()>1){
			int a=vec[i][0],b=vec[i][1];
			w[i][2]=x[i]+x[b];
			v[i][2]=v[i][0]+x[b]*y[b];
			w[i][3]=w[i][1]+x[b];
			v[i][3]=v[i][1]+x[b]*y[b];
		}
	}
}

int main(){
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	ios::sync_with_stdio(false);
	init();
	for(int i=1;i<=n;i++)if(o[i]){
		for(int j=m;j>=0;j--){
			if(j>=w[i][0])
				f[j]=max(f[j],f[j-w[i][0]]+v[i][0]);
			if(vec[i].size()&&j>=w[i][1])
				f[j]=max(f[j],f[j-w[i][1]]+v[i][1]);
			if(vec[i].size()>1){
				if(j>=w[i][2])
					f[j]=max(f[j],f[j-w[i][2]]+v[i][2]);
				if(j>=w[i][3])
					f[j]=max(f[j],f[j-w[i][3]]+v[i][3]);
			}
		}
	}
	cout<<f[m]<<endl;
	return 0;
}