记录编号	566494	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2021-11-09 20:35:50	内存使用	5.98 MiB

#include<bits/stdc++.h>
#define ull unsigned long long 
#define ll long long 
using namespace std;
int st[65];
int vc,nc;
struct wj
{
	int g;
	int p;
	int vl;
	int nx;
}n[65]; 
int p[65];
int f[32005];
void BUILD(int x,int y)
{
	n[x].nx=st[y];
	st[y]=x;
	return;
}
void BB(int cl)
{
	for(int i=vc;i>=n[cl].p;i--) f[i]=max(f[i],f[i-n[cl].p]+n[cl].vl);
//    cout<<cl<<":"<<f[vc]<<" "<<n[cl].vl<<endl;
	return;
}
int a[32005];
void FZBB(int cl)
{
	for(int i=vc;i>=n[cl].p;i--) a[i]=f[i-n[cl].p]+n[cl].vl;
	int s1=st[cl];
	while(s1)
	{
		for(int i=vc;i-n[s1].p>=n[cl].p;i--) a[i]=max(a[i],a[i-n[s1].p]+n[s1].vl);
		s1=n[s1].nx;
	}
	for(int i=vc;i>=n[cl].p;i--) f[i]=max(f[i],a[i]);
//	cout<<cl<<":"<<f[vc]<<" "<<n[cl].vl<<endl;
	return;
}
int main()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
    scanf("%d%d",&vc,&nc);
    vc/=10;
    for(int i=1;i<=nc;i++)
    {
    	scanf("%d%d%d",&n[i].p,&n[i].g,&n[i].nx);
    	if(!n[i].nx) p[i]=1;
    	n[i].p/=10;
    	n[i].vl=n[i].p*n[i].g;
    	if(n[i].nx) BUILD(i,n[i].nx);
    }
    for(int i=1;i<=nc;i++) 
	{
		if(p[i]&&!st[i]) BB(i);
		else if(p[i]) FZBB(i);
	}
//	for(int i=1;i<=vc;i++) cout<<i<<":"<<f[i]<<endl;
//    for(int i=1;i<=nc;i++)
//    {
//    	int s1=st[i];
//    	cout<<i<<":\n";
//    	while(s1&&s1!=-1)
//    	{
//    		cout<<s1<<" ";
//    		s1=n[s1].nx;
//    	}
//    	cout<<"\ned\n\n";
//    }
    printf("%d\n",f[vc]*10);
    return 0;
}