记录编号	20397	评测结果	AAAAAAAAAA
题目名称	逛街	最终得分	100
用户昵称	郭乾乐	是否通过	通过
代码语言	C++	运行时间	0.162 s
提交时间	2010-10-25 22:21:12	内存使用	116.35 MiB

#include<iostream>
#include<fstream>
using namespace std;
int f[301][1001][101];
int main()
{
	ifstream fin("shop.in");
	ofstream fout("shop.out");
	int n,m,z,i,j,k,r,v[301],t[301],w[301],s[301];
	fin>>n>>z>>m;
	for(i=1;i<=n;i++)
		fin>>w[i]>>v[i]>>t[i]>>s[i];
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			for(k=1;k<=z;k++)
			{
				f[i][j][k]=f[i-1][j][k];
				if(j>=v[i]&&k>=w[i])
				    if((f[i-1][j-v[i]][k-w[i]]+t[i])>f[i][j][k])
						f[i][j][k]=f[i-1][j-v[i]][k-w[i]]+t[i];
				if(j>=v[i]*s[i]&&k>=w[i]*s[i])
					if((f[i-1][j-v[i]*s[i]][k-w[i]*s[i]]+t[i]*s[i])>f[i][j][k])
						f[i][j][k]=f[i-1][j-v[i]*s[i]][k-w[i]*s[i]]+t[i]*s[i];
			}
	fout<<f[n][m][z];
	return 0;
}