记录编号	419943	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2017-07-03 17:26:12	内存使用	1.60 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=32010;
const int maxm=70;
int n,m;
int f[maxn];
struct bao{
	int w[5],c[5];
	int tot;//附件个数 
};
bao wupin[maxn];
int tot;
int mk[maxm];
int main(){
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int v,p,q;
		scanf("%d%d%d",&v,&p,&q);
		if(q==0){
			++tot; 
			mk[i]=tot;
			for(int j=1;j<=4;j++){
				wupin[tot].w[j]+=v;
			}
			for(int j=1;j<=4;j++){
				wupin[tot].c[j]+=v*p;
			}
		}
		else{
			wupin[mk[q]].tot++;
			wupin[mk[q]].w[wupin[mk[q]].tot+1]+=v;
			wupin[mk[q]].c[wupin[mk[q]].tot+1]+=v*p;
			wupin[mk[q]].w[4]+=v;
			wupin[mk[q]].c[4]+=v*p;
			if(wupin[mk[q]].tot==2)wupin[mk[q]].tot++;
		}
	}
	for(int k=1;k<=tot;k++){
		for(int v=n;v>=0;v--){
			for(int i=1;i<=wupin[k].tot+1;i++){
				if(v-wupin[k].w[i]>=0)f[v]=max(f[v],f[v-wupin[k].w[i]]+wupin[k].c[i]);
			}
		}
	}
	printf("%d\n",f[n]);
	return 0;
}