记录编号	247927	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	GaoErFu	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2016-04-09 20:43:53	内存使用	1.41 MiB

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int v[110000]={0},c[110000]={0},f[32010]={0},q[110][15]={0},t[70][1100]={0};
int ccc()
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	int N,m,n,s,i,j,k,l,r,x,y,z,num=0,numi;
	scanf("%d%d%d",&N,&m,&s);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 
		{
			v[i]=x;
			c[i]=y*v[i];
			q[z][0]++;
			q[z][q[z][0]]=i;
		}
	}
	for(i=1;i<=n;i++)
	{
		if(q[i][0]!=0)
		{memset(f,0,sizeof(f));
		for(l=1;l<=q[i][0];l++)
		for(r=N-v[i];r>=v[q[i][l]];r--)
		{
			if(r>=v[q[i][l]]&&f[r-v[q[i][l]]]+c[q[i][l]]>f[r])
		    f[r]=f[r-v[q[i][l]]]+c[q[i][l]];
		}
		for(l=1;l<=N-v[i];l++)
		{
			if(f[l]>f[l-1])
			{
				m++;
				v[m]=l+v[i];
				c[m]=f[l]+c[i];
				t[i][++t[i][0]]=m;
			}
		}
		}
	}
	memset(f,0,sizeof(f));
	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=ccc();
int main(){;}