记录编号	163242	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2015-05-23 18:47:24	内存使用	2.31 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int qian,n,a[102][102];
int b[102][102],za[45000];
int qiann[3000],num,zhong[3000];
int f[450000],nnum;
bool s[96];
int main()
{   freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
  cin>>qian>>n;
  for(int i=1;i<=n;++i)
  {     int p;
		cin>>qiann[i]>>zhong[i]>>p;
		za[i]=qiann[i]*zhong[i];
		if(p!=0)
		{
			a[p][++a[p][0]]=i;
		}
		else
		 {
				a[i][++a[i][0]]=i;
		 }
  }
  /*for(int i=1;i<=3;++i)
   cout<<za[a[1][i]]<<" "<<qiann[a[1][i]]<<endl;*/
   int m=n;
  for(int i=1;i<=n;++i)
   {
	  if(a[i][0]==1)
	      {     nnum++;
				b[nnum][0]++;
				b[nnum][b[nnum][0]]=a[i][1];
	      }
      if(a[i][0]==2)
      {
	     nnum++;
	     b[nnum][0]+=2;
	     b[nnum][1]=a[i][1];
		 za[b[nnum][1]]=za[a[i][1]];
		 qiann[b[nnum][1]]=qiann[a[i][1]];
		 m++;
		 b[nnum][2]=m;
	     za[b[nnum][2]]=za[a[i][1]]+za[a[i][2]];
	     qiann[b[nnum][2]]=qiann[a[i][1]]+qiann[a[i][2]];
       }
      if(a[i][0]==3)
      {   //cout<<i<<endl<<endl;
		nnum++;
		b[nnum][0]+=4;
		b[nnum][1]=a[i][1];
		za[b[nnum][1]]=za[a[i][1]];
		qiann[b[nnum][1]]=qiann[a[i][1]];
		m++;
		b[nnum][2]=m;
        za[b[nnum][2]]=za[a[i][1]]+za[a[i][2]];
	    qiann[b[nnum][2]]=qiann[a[i][1]]+qiann[a[i][2]];
	    m++;
	    b[nnum][3]=m;
	    za[b[nnum][3]]=za[a[i][1]]+za[a[i][3]];
	    qiann[b[nnum][3]]=qiann[a[i][1]]+qiann[a[i][3]];
	    m++;
	    b[nnum][4]=m;
	    za[b[nnum][4]]=za[a[i][1]]+za[a[i][2]]+za[a[i][3]];
	    qiann[b[nnum][4]]=qiann[a[i][1]]+qiann[a[i][2]]+qiann[a[i][3]];
       }

   }
   /*for(int i=1;i<=nnum;++i)
	{
		for(int j=1;j<=b[i][0];++j)
		  cout<<qiann[b[i][j]]<<" "<<za[b[i][j]]<<endl;
		cout<<"LLLL"<<endl;
	}*/
  for(int i=1;i<=nnum;++i)
	 for(int j=qian;j>=0;--j)
      for(int k=1;k<=b[i][0];++k)
       if(j>=qiann[b[i][k]])
       {
            int haha=b[i][k];
            if(f[j]<f[j-qiann[haha]]+za[haha])
			   f[j]=f[j-qiann[haha]]+za[haha];
       }
	cout<<f[qian];
	//system("pause");
}