记录编号 |
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;
}