记录编号	187561	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2015-09-19 15:33:19	内存使用	0.42 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define w0 g[i].pri*g[i].imp
#define v0 g[i].pri
#define w1 g[g[i].c1].pri*g[g[i].c1].imp
#define v1 g[g[i].c1].pri
#define w2 g[g[i].c2].pri*g[g[i].c2].imp
#define v2 g[g[i].c2].pri
using namespace std;

int n, m, e, w[245], v[245];
int f[32005]; 

struct goods{
	int pri, imp;
	int q, c1, c2;
}g[66];

int main()
{
	freopen("budget.in","r",stdin);
    freopen("budget.out","w",stdout);
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++){
		scanf("%d %d %d", &g[i].pri, &g[i].imp, &g[i].q);
		g[g[i].q].c2 = g[g[i].q].c1;
		g[g[i].q].c1 = i;
	}
	for(int i = 1; i <= m; i++){
		if(g[i].q) continue;
		w[++e] = w0;
		v[e] = v0;
		w[++e] = w0 + w1;
		v[e] = v0 + v1;
		w[++e] = w0 + w2;
		v[e] = v0 + v2;
		w[++e] = w0 + w1 + w2;
		v[e] = v0 + v1 + v2;
	}

	for(int i = 1; i <= e; i += 4)
	for(int j = n; j >= 0; j--)
	for(int k = 0; k < 4; k++){
		if(j-v[i+k] < 0) continue;
		f[j] = max(f[j], f[j-v[i+k]] + w[i+k]);
	}
	printf("%d", f[n]);
	return 0;
}