记录编号	449376	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	FFF团	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2017-09-14 09:42:19	内存使用	0.44 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,t1,t2,t3,v[4][65],w[4][65],f[32005];
int main(){
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>t1>>t2>>t3;
		if(!t3){
			v[0][i]=v[3][i]=t1*t2;
			w[0][i]=w[3][i]=t1;
		}
		else{
			for(int j=1;j<=2;j++)
			if(!v[j][t3]){
				v[j][t3]=t1*t2+v[0][t3];
				w[j][t3]=t1+w[0][t3];
				v[3][t3]+=t1*t2;
				w[3][t3]+=t1;
				break;
			}
		}
	}
	
	/*
	for(int i=1;i<=m;i++)
	for(int j=0;j<=3;j++)
	cout<<i<<":"<<v[j][i]<<" "<<w[j][i]<<endl;
	*/
	
	for(int k=1;k<=m;k++)
	for(int j=n;j>=0;j--)
	for(int i=0;i<=3;i++)
	if(j>=w[i][k])f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);
	cout<<f[n];
	return 0;
}