记录编号	468476	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2017-11-01 10:56:47	内存使用	0.48 MiB

#include<cstdio>
#include<iostream>
using namespace std;
inline int get();
int n,m;
int v[61],p[61],q[61],mmp[61][61],temp[61];
int dp[40001];
int main()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	n=get(),m=get();
	for(int i=1;i<=m;i++)
	{
		v[i]=get();
		p[i]=get();
		q[i]=get();
		if(q[i])mmp[q[i]][temp[q[i]]++]=i;
	}
	for(int i=1;i<=m;i++)
	{
		if(q[i])continue;
		for(int j=n;j>=0;j--)
		{
			int a(0),b(0),c(0),d(0);
			int ta=mmp[i][0],tb=mmp[i][1];
			if(j>=v[i])a=dp[j-v[i]]+v[i]*p[i];
			if(ta&&j>=v[i]+v[ta])b=dp[j-v[i]-v[ta]]+v[i]*p[i]+v[ta]*p[ta];
			if(tb&&j>=v[i]+v[tb])c=dp[j-v[i]-v[tb]]+v[i]*p[i]+v[tb]*p[tb];
			if(ta&&tb&&j>=v[i]+v[ta]+v[tb])d=dp[j-v[i]-v[ta]-v[tb]]+v[i]*p[i]+v[ta]*p[ta]+v[tb]*p[tb];
			dp[j]=max(dp[j],max(max(a,b),max(c,d)));
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}
inline int get()
{
	int t=0;char c=getchar(),j=1;
	while(!isdigit(c))
		if(c=='-')j=-1,c=getchar();
		else c=getchar();
	while(isdigit(c))
		t=(t<<3)+(t<<1)+c-'0',
		c=getchar();
	return j*t;
}