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

//时间:1s  空间:128MB
//题意:给定m元n个物品,在不超过m的前提下,最大化价值*重要度的和
//每个物品可以是主件或者附件,附件需要够买主件
//算法:有依赖的背包问题,可以枚举主件,因为最多只有2个附件,
//那么最多有4种情况,只取主件,取1号附件,取2号附件,或者两个都取
//然后和01背包无差
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
vector<int>G[65];
int w[65],v[64],q[65];
int dp[32005];
int main(){
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	int m,n;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&w[i],&v[i],&q[i]);
		v[i]*=w[i];
		if(q[i])G[q[i]].push_back(i);	
	}
	for(int i=1;i<=n;i++){
		if(q[i])continue;
		int t1=0,t2=0;
		if(G[i].size()>=1)t1=G[i][0];
		if(G[i].size()>=2)t2=G[i][1];
		for(int j=m;j>=w[i];j--){
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
			if(t1!=0&&j-w[i]-w[t1]>=0)
				dp[j]=max(dp[j],dp[j-w[i]-w[t1]]+v[i]+v[t1]);
			if(t2!=0&&j-w[i]-w[t2]>=0)
				dp[j]=max(dp[j],dp[j-w[i]-w[t2]]+v[i]+v[t2]);
			if(t1!=0&&t2!=0&&j-w[i]-w[t1]-w[t2]>=0)
				dp[j]=max(dp[j],dp[j-w[i]-w[t1]-w[t2]]+v[i]+v[t1]+v[t2]);
		}
	}
	printf("%d\n",dp[m]);
	return 0;
}