记录编号	245156	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	GaoErFu	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-02 12:13:43	内存使用	0.00 MiB

#include<stdio.h>
int v[1010]={0},c[1010]={0},f[32010]={0},q[100][4]={0},t[110][110]={0};
int cc()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	int N,m,n,i,j,k,x,y,z,num=0;
	scanf("%d%d",&N,&m);n=m;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		if(z==0)
		{
			v[i]=x;
			c[i]=y*v[i];
			t[i][++t[i][0]]=i;
		}
		else 
		{
			q[++num][1]=x;
			q[num][2]=x*y;
			q[num][3]=z;
		}
	}
	for(i=1;i<=num;i++)
	{
		k=i;
		while(q[i][3]==q[k][3])
		k++;
		k--; 
		if(k-i==0)
		{
			m++;
			t[q[k][3]][++t[q[k][3]][0]]=m;
			v[m]=q[k][1]+v[q[k][3]];
			c[m]=q[k][2]+c[q[k][3]];
		}
		else if(k-i==1)
		{
			m++;
			t[q[i][3]][++t[q[i][3]][0]]=m;
			v[m]=q[i][1]+v[q[i][3]];
			c[m]=q[i][2]+c[q[i][3]];
			m++;
			t[q[k][3]][++t[q[k][3]][0]]=m;
			v[m]=q[k][1]+v[q[k][3]];
			c[m]=q[k][2]+c[q[k][3]];
			m++;
			t[q[k][3]][++t[q[k][3]][0]]=m;
			v[m]=q[k][1]+v[q[k][3]]+q[i][1];
			c[m]=q[k][2]+c[q[k][3]]+q[i][2];
		}
		i=k;
	}
	for(i=1;i<=n;i++)
	{if(t[i][0]==0)continue;
	for(j=N;j>=1;j--)
	{
		for(k=1;k<=t[i][0];k++)
		if(j>=v[t[i][k]]&&f[j-v[t[i][k]]]+c[t[i][k]]>f[j])
		f[j]=f[j-v[t[i][k]]]+c[t[i][k]];
	}
	}
	printf("%d",f[N]);
	return 0;
}
int xxx=cc();
int main(){;}