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

#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXM=33000;
const int MAXN=100;
const int MAXS=12;
int N,M,S,F[MAXN][MAXM]={0},MF=0;
class MainFile
{
public:int child,value,price;
int cvalue[MAXS],cprice[MAXS];
}E[MAXN];
int MFBag[MAXN][MAXM]={0};

inline void init()
{
	scanf("%d %d %d\n",&M,&N,&S); M/=10;
	int tvv[MAXM]={0},
		tpp[MAXN]={0},
		tbb[MAXN]={0},
		tmf[MAXN]={0};
	for(int i=1;i<=N;i++)
	{
		scanf("%d %d %d\n",&tpp[i],&tvv[i],&tbb[i]);
		if(tbb[i]==0)
		{
			MF++;E[MF].value=tvv[i];tmf[i]=MF;
			E[MF].price=tpp[i]/10; E[MF].child=0;
		} 
	}	int tmp;
	for(int i=1;i<=N;i++)
	{
		if(!tbb[i]) continue;
		tmp=tmf[tbb[i]]; E[tmp].child++;
		E[tmp].cvalue[E[tmp].child]=tvv[i];
		E[tmp].cprice[E[tmp].child]=tpp[i]/10;
	} 
} 
inline int Max(int a,int b){return a>b?a:b;}
inline void dp()
{
	for(int i=1;i<=MF;i++)
	{
		for(int j=1;j<=E[i].child;j++)
			for(int k=M;k>=E[i].price+E[i].cprice[j];k--)
				MFBag[i][k]=Max(MFBag[i][k],
					MFBag[i][k-E[i].cprice[j]]+E[i].cvalue[j]*E[i].cprice[j]);
		for(int j=M;j>=0;j--) F[i][j]=F[i-1][j];
		for(int j=M;j>=E[i].price;j--)
		{
			for(int k=E[i].price;k<=j;k++)
				F[i][j]=Max(F[i][j],F[i-1][j-k]+MFBag[i][k]+E[i].price*E[i].value);
		}
	}
	printf("%d\n",F[MF][M]*10);
}

int main()
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	init(); dp();
	return 0;
}