记录编号	49570	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2012-11-08 15:14:01	内存使用	61.53 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,s,w[100][3],q[5000][3205]={0},answer=0,num=0;
vector<int>con[100];
vector<int>val[100];
vector<int>wei[100];
int f[10000][2]={0},o;
void dfs(int x,int y,int z,int k);
int main()
{
	freopen ("budgetb.in","r",stdin);
	freopen ("budgetb.out","w",stdout);\
	
	cin>>n>>m>>s;
	for (int i=1;i<=m;i++)
	{
		cin>>w[i][0]>>w[i][1]>>w[i][2];
		w[i][0]/=10;
		if (w[i][2]>0)
		{
			con[w[i][2]].push_back(i);
		}
		if (w[i][2]==0)
		{
			val[i].push_back(w[i][0]);
			wei[i].push_back(w[i][0]*w[i][1]);
		}
	}
	for (o=1;o<=m;o++)
	{
		if (con[o].size()>0)
		{
			dfs(0,0,0,0);
		}
	}
	for (int i=1;i<=m;i++)
	{
		if (con[i].size()==0&&w[i][2]==0)
		{
			for (int j=n/10;j>=0;j--)
			{
				q[i][j]=q[num][j];
				if (j-w[i][0]>=0)
				{
					q[i][j]=max(q[i][j],q[num][j-w[i][0]]+w[i][1]*w[i][0]);
					if (q[i][j]>answer)
						answer=q[i][j];
				}
			}
			num=i;
		}
		if (val[i].size()>1&&w[i][2]==0)
		{
			for (int j=n/10;j>=0;j--)
			{
				q[i][j]=q[num][j];
				for (int k=0;k<val[i].size();k++)
				{
					if (j-val[i][k]>=0)
					{
						q[i][j]=max(q[i][j],q[num][j-val[i][k]]+wei[i][k]);
						if (q[i][j]>answer)
							answer=q[i][j];
					}
				}
			}
			num=i;
		}
	}
	cout<<answer*10;
	return 0;
}

void dfs(int x,int y,int z,int k)
{
	if (x==con[o].size()&&k<=s)
	{
		if (y==0)
			return;
		val[o].push_back(y+w[o][0]);
		wei[o].push_back(z+w[o][1]*w[o][0]);
		return;
	}
	for (int i=0;i<2;i++)
	{
		dfs(x+1,y+w[con[o][x]][0]*i,z+w[con[o][x]][1]*i*w[con[o][x]][0],k+i);
	}
}