记录编号	49585	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.762 s
提交时间	2012-11-08 15:35:43	内存使用	3.96 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;
 
int weii[65],vall[65],to[65];
int numnofu,weinofu[65],valnofu[65];
int num,val[65][3210];
int numfu,limfu,weifu[65],valfu[65];
int f[3210];
 
int main(void)
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	int i,j,k,lim,n,s;
	cin>>lim>>n>>s;
	lim/=10;
	for (i=1;i<=n;i++)
	{
		cin>>weii[i]>>vall[i]>>to[i];
		vall[i]*=weii[i];
		weii[i]/=10;
	}
	for (i=1;i<=n;i++)
		if (to[i]==0)
		{
			numfu=0;
			for (j=1;j<=n;j++)
				if (to[j]==i)
				{
					numfu++;
					weifu[numfu]=weii[j];
					valfu[numfu]=vall[j];
				}
			if (numfu==0)
			{
				numnofu++;
				weinofu[numnofu]=weii[i];
				valnofu[numnofu]=vall[i];
				continue;
			}
			limfu=lim-weii[i];
			num++;
			for (j=weii[i];j<=lim;j++)
				val[num][j]=vall[i];
			for (j=1;j<=numfu;j++)
				for (k=limfu;k>=weifu[j];k--)
					f[k]=max(f[k],f[k-weifu[j]]+valfu[j]);
			for (j=weii[i],k=0;j<=lim;j++,k++)
				val[num][j]+=f[k];
			memset(f,0,sizeof(f));
		}
	for (i=1;i<=numnofu;i++)
		for (j=lim;j>=weinofu[i];j--)
			f[j]=max(f[j],f[j-weinofu[i]]+valnofu[i]);
	for (i=1;i<=num;i++)
		for (j=lim;j>=1;j--)
			for (k=0;k<j;k++)
				f[j]=max(f[j],f[k]+val[i][j-k]);
	cout<<f[lim]<<endl;
	return(0);
}