记录编号	28365	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2011-10-13 20:50:17	内存使用	0.99 MiB

#include <cstdio>
using namespace std;

int f[60][3200]={{0}};

int main(void)
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	int i,j,mon,n,pri[60],val[60],typ[60],exnum[60]={0},expos[60][2];
	mon/=10;
	scanf("%d %d",&mon,&n);
	mon/=10;
	for (i=1;i<=n;i++)
	{
		scanf("%d %d %d",&pri[i],&val[i],&typ[i]);
		val[i]=val[i]*pri[i];
		pri[i]/=10;
		if (typ[i]!=0)
			expos[typ[i]][exnum[typ[i]]++]=i;
	}
	for (i=1;i<=n;i++)
		if (typ[i]!=0)
			for (j=1;j<=mon;j++)
				f[i][j]=f[i-1][j];
		else
			for (j=1;j<=mon;j++)
			{
				/**/
				int temp,temppri;
				f[i][j]=f[i-1][j];
				if (j>=pri[i])
				{
					temp=val[i]+f[i-1][j-pri[i]];
					if (temp>f[i][j])
						f[i][j]=temp;
					if (exnum[i]==1||exnum[i]==2)
					{
						temppri=pri[i]+pri[expos[i][0]];
						if (j>=temppri)
						{
							temp=val[i]+val[expos[i][0]]+f[i-1][j-temppri];
							if (temp>f[i][j])
								f[i][j]=temp;
						}
						if (exnum[i]==2)
						{
							temppri=pri[i]+pri[expos[i][1]];
							if (j>=temppri)
							{
								temp=val[i]+val[expos[i][1]]+f[i-1][j-temppri];
								if (temp>f[i][j])
									f[i][j]=temp;
							}
							temppri=pri[i]+pri[expos[i][0]]+pri[expos[i][1]];
							if (j>=temppri)
							{
								temp=val[i]+val[expos[i][0]]+val[expos[i][1]]+f[i-1][j-temppri];
								if (temp>f[i][j])
									f[i][j]=temp;
							}
						}
					}
				}
				/**/
			}
	printf("%d\n",f[n][mon]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}