记录编号	34335	评测结果	AAAAAAAAAA
题目名称	117.[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2011-12-10 16:39:32	内存使用	1.01 MiB

#include <fstream>
using namespace std;
ifstream fin("budget.in");
ofstream fout("budget.out");
int mgn,m,n,f[61][3201];
class SUB
{
public:
	int SV,SP;
};
class
{
public:
	int Value,Price,subnum;
	SUB sub[3];
}maingoods[61];
class node
{
public:
	int pp,vv,ii;
}A[61];
void Init()
{
int NodePos[61];
	fin>>n>>m;n/=10;
	for(int i=1;i<=m;i++)
	{
		fin>>A[i].pp>>A[i].vv>>A[i].ii;
		if(A[i].ii==0)
			NodePos[i]=++mgn;
	}
	mgn=0;
	for(int i=1;i<=m;i++)
	{
		if(A[i].ii==0)
		{
			maingoods[++mgn].Price=A[i].pp/10;
			maingoods[mgn].Value=A[i].vv;
		}
		else
		{
			++maingoods[NodePos[A[i].ii]].subnum;
			maingoods[NodePos[A[i].ii]].sub[maingoods[NodePos[A[i].ii]].subnum].SP=A[i].pp/10;
			maingoods[NodePos[A[i].ii]].sub[maingoods[NodePos[A[i].ii]].subnum].SV=A[i].vv;
		}
	}
}

void dp()
{
int i,k,j,Max;
	for(i=1;i<=mgn;i++)
		for(j=1;j<=n;j++)
		{
			int Pm=maingoods[i].Price;
			int Pi[3]={0,maingoods[i].sub[1].SP,maingoods[i].sub[2].SP};
			int Vm=maingoods[i].Value;
			int Vi[3]={0,maingoods[i].sub[1].SV,maingoods[i].sub[2].SV};
			Max=0;
			if(j>=Pm)
			{
				Max=f[i-1][j];
				if(f[i-1][j-Pm]+Pm*Vm>Max)
					Max=f[i-1][j-Pm]+Pm*Vm;
				for(k=1;k<=2;k++)
					if(Pi[k]+Pm <= j)
						if(f[i-1][j-Pi[k]-Pm]+Pi[k]*Vi[k]+Pm*Vm > Max)
							Max=f[i-1][j-Pi[k]-Pm]+Pi[k]*Vi[k]+Pm*Vm;
				if(Pi[1]+Pi[2]+Pm <=j)
					if(f[i-1][j-Pi[1]-Pi[2]-Pm]+Pi[1]*Vi[1]+ Pi[2]*Vi[2] + Pm*Vm > Max)
						Max=f[i-1][j-Pi[1]-Pi[2]-Pm]+Pi[1]*Vi[1]+ Pi[2]*Vi[2] + Pm*Vm;
					
				f[i][j]=Max;
			}
			else
				f[i][j]=f[i-1][j];
		}
}

int main()
{
	Init();
	
	dp();
	
	fout<<f[mgn][n]*10<<endl;
	fin.close();
	fout.close();
	return 0;
}