[JSOI 2008] 魔兽地图

题目大意

给定 nn 个装备和数量为 mm 的金钱,求可获得的最大力量。其中,每个装备有一个力量值,同时装备分为基本装备和高级装备,基本装备给定了价格和数量限制,高级装备需要一些其他装备来合成(需要哪些、需要几个已给定)。

1n511 \leqslant n \leqslant 51

1m2,0001 \leqslant m \leqslant 2,000

1limit1001 \leqslant limit \leqslant 100(数量限制)

题目链接

【JSOI 2008】魔兽地图 - Luogu 4037

题解

树形 DP。

对于每一个节点 xx,有一个 f[i,  j]f[i, \; j],表示花费 jj 的金钱、有 iixx 被用于合成高一级的装备时的最大力量。在转移时,定义一个辅助数组 g[i,  j]g[i, \; j],表示当前节点的子节点中,已经考虑了 ii 个、花费为 jj 的最大力量。记 tottot 为一个节点字节点数,则转移为(当前节点为 xx):

枚举 xx 的合成量 ll

g[i,  j]=max(g[i1,  jk]+v.f[l×num(v>x),  k]),  v  is  son  of  xg[i, \; j] = max(g[i - 1, \; j - k] + v.f[l \times num(v->x), \; k]), \; v \; is \; son \; of \; x

再枚举其中的 ii 个用于合成高一级装备:

x.f[i,  j]=max(g[tot,  j]+x.price×(li))x.f[i, \; j] = max(g[tot, \; j] + x.price \times (l - i))

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
// #define DBG
const int MAXN = 55;
const int MAXLIMIT = 105;
const int MAXM = 2005;
struct Edge;
struct Node {
Edge *e;
int strength, limit, price, deg;
int f[MAXLIMIT][MAXM];
#ifdef DBG
int id;
#endif
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next;
int w;
Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
};
void addEdge(int u, int v, int w) {
N[u].e = new Edge(&N[u], &N[v], w);
N[v].deg++;
}
int n, m;
int g[MAXN][MAXM];
void dp(Node *u) {
#ifdef DBG
printf("dp(%d)\n", u->id);
#endif
if (!u->e) {
u->limit = std::min(u->limit, m / u->price);
for (int i = 0; i <= u->limit; i++) {
for (int j = i; j <= u->limit; j++)
u->f[i][j * u->price] = (j - i) * u->strength;
}
#ifdef DBG
printf("end dp(%d), limit = %d\n", u->id, u->limit);
#endif
return;
}
u->limit = INT_MAX;
for (Edge *e = u->e; e; e = e->next) {
dp(e->v);
u->limit = std::min(u->limit, e->v->limit / e->w);
u->price += e->v->price * e->w;
}
u->limit = std::min(u->limit, m / u->price);
#ifdef DBG
printf("end calcLimit(%d), limit = %d\n", u->id, u->limit);
#endif
memset(g, -0x3f3f3f3f, sizeof (g));
g[0][0] = 0;
for (int l = u->limit; l >=0; l--) {
int tot = 0;
for (Edge *e = u->e; e; e = e->next) {
tot++;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= i; j++)
g[tot][i] = std::max(g[tot][i],
g[tot - 1][i - j] + e->v->f[e->w * l][j]);
}
}
for (int i = 0; i <= l; i++) {
for (int j = 0; j <= m; j++)
u->f[i][j] = std::max(u->f[i][j], g[tot][j] + (l - i) * u->strength);
}
}
}
int main() {
scanf("%d %d", &n, &m);
#ifdef DBG
for (int i = 1; i <= n; i++) N[i].id = i;
#endif
for (int i = 1; i <= n; i++) {
char type[2];
scanf("%d %c", &N[i].strength, type);
if (type[0] == 'A') {
int c;
scanf("%d", &c);
for (int j = 0; j < c; j++) {
int x, num;
scanf("%d %d", &x, &num);
addEdge(i, x, num);
}
} else scanf("%d %d", &N[i].price, &N[i].limit);
}
for (int i = 1; i <= n; i++) memset(N[i].f, -0x3f3f3f3f, sizeof (N[i].f));
static int h[MAXN][MAXM];
int tot = 0;
for (int x = 1; x <= n; x++) {
#ifdef DBG
printf("x = %d\n", x);
#endif
if (N[x].deg == 0) {
dp(&N[x]);
tot++;
#ifdef DBG
printf("tot = %d\n", tot);
#endif
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= N[x].limit; k++) {
h[tot][i] = std::max(h[tot][i],
h[tot - 1][j] + N[x].f[k][i - j]);
}
}
}
}
}
int ans = 0;
for (int i = 0; i <= m; i++) ans = std::max(ans, h[tot][i]);
printf("%d\n", ans);
return 0;
}