记录编号	348878	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	龙征天	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-11-14 17:11:39	内存使用	2.52 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct node
{
	int w[100],v[100];
};
const int maxn=32000+10;
node q[100];
int f[100][maxn];
int n,m,max1;
int getint();
int tian()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	
	m=getint(); n=getint();
	for(int i=1; i<=n; i++) 
	{
		int x,y,z;
		x=getint(); y=getint(); z=getint();
		if(z==0)//主件 
		{
			q[i].v[1]=x;
			q[i].w[1]=x*y;
		}
		else//附件 
		{
			if(q[z].v[2]!=0)
			{
				q[z].v[3]=x;
				q[z].w[3]=x*y;
			}
			else
			{
				q[z].v[2]=x;
				q[z].w[2]=x*y;
			}
		}
	}
	
	for(int i=1; i<=n; i++)//转成每种情况 
	{
		q[i].v[4]=q[i].v[3]+q[i].v[2]+q[i].v[1];//主件1和附件23
		q[i].w[4]=q[i].w[3]+q[i].w[2]+q[i].w[1];
		
		q[i].v[2]=q[i].v[2]+q[i].v[1];//主件1和附件2 
		q[i].w[2]=q[i].w[2]+q[i].w[1];
		
		q[i].v[3]=q[i].v[3]+q[i].v[1];//主件1和附件3 
		q[i].w[3]=q[i].w[3]+q[i].w[1];
		
		q[i].v[5]=0;//不选 
		q[i].w[5]=0;
	}
	
	for(int i=1; i<=n; i++)
	for(int j=1; j<=m; j++)
	{
		f[i][j]=f[i-1][j];
 		for(int k=1; k<=5; k++)//分组背包 
		{
			if(j-q[i].v[k]>=0)
			{
				if(f[i-1][j-q[i].v[k]]+q[i].w[k]>f[i][j])
					f[i][j]=f[i-1][j-q[i].v[k]]+q[i].w[k];
			}
		}
	}
	
	printf("%d\n",f[n][m]);
	
	return 0;
}
int tian1=tian();
int main()
{
	;
}
int getint()
{
	int x=0,s=1;
	char ch=' ';
	while(ch<'0' || ch>'9')
	{
		ch=getchar();
		if(ch=='-') s=-1;
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*s;
}