记录编号	234341	评测结果	AWWWWWWWWA
题目名称	[NOIP 2006]金明的预算方案	最终得分	20
用户昵称	Aeons	是否通过	未通过
代码语言	C++	运行时间	0.066 s
提交时间	2016-03-07 21:24:27	内存使用	15.58 MiB

#include <fstream>
using namespace std;
int v[100],w[100],f[100][40000],price[100][10],imp[100][10],m[200];
int main()
{
	ifstream fin("budget.in");
	ofstream fout("budget.out");
	int n,x,i,j,s,count=0;
	fin>>x>>n;
	for(i=0;i<n;i++)
	{
		for(j=0;j<32000;j++)
			f[i][j]=0;
	}
	for(i=0;i<n;i++)
	{
		fin>>v[i]>>w[i]>>m[i];
	}
	for(i=0;i<n;i++)
	{
		if(m[i]==0)
		{
			s=count;
			price[s][0]++;
			count++;
			price[s][1]=v[i];
			imp[s][1]=v[i]*w[i];
		}
		if(m[i]==count)
		{
			price[s][0]++;
			if(price[s][0]==2)
			{
				price[s][2]=price[s][1]+v[i];
				imp[s][2]=imp[s][1]+v[i]*w[i];
			}
			if(price[s][0]==3)
			{
				price[s][3]=price[s][1]+v[i];
				imp[s][3]=imp[s][1]+v[i]*w[i];
				
			}price[s][4]=price[s][2]+price[s][3]-price[s][1];
				imp[s][4]=imp[s][2]+imp[s][3]-imp[s][1];
		} 
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=x;j++)
	{
		if(price[i-1][1]>j)
			f[i][j]=f[i-1][j];
	    else
		{
			f[i][j]=f[i-1][j];
			for(int b=1;b<=4;b++)
				if(j>=price[i-1][b])
					f[i][j]=max(f[i][j],f[i-1][j-price[i-1][b]]+imp[i-1][b]);
		}
	}
	fout<<f[n][x]<<endl;
	fin.close();
	fout.close();
	return 0;
}