「BZOJ1017」[JSOI2008]魔兽地图DotR

Description

DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图,他的规则简单与同样流行的地图DotA (Defense of the Ancients) Allstars。

DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值,每件装备都可以使佩戴它的英雄的力量值提高固定的点数,所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买,而高级装备需要用基本装备或者较低级的高级装备来合成,合成不需要附加的金币。装备的合成路线可以用一棵树来表示。

比如,Sange and Yasha的合成需要Sange,YashaSange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant StrengthSange Recipe Scroll合成。每件基本装备都有数量限制,这限制了你不能无限制地合成某些性价比很高的装备。

现在,英雄Spectre有MM个金币,他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他吗?他会教你魔法Haunt(幽灵附体)作为回报的。

Input

第一行包含两个整数,N(1n51)N (1 \leq n \leq 51)m(0m2,000)m (0 \leq m \leq 2,000)。分别表示装备的种类数和金币数。装备用11NN的整数编号。
接下来的NN行,按照装备11到装备nn的顺序,每行描述一种装备。
每一行的第一个非负整数表示这个装备贡献的力量值。
接下来的非空字符表示这种装备是基本装备还是高级装备,A表示高级装备,B表示基本装备。如果是基本装备,紧接着的两个正整数分别表示它的单价(单位为金币)和数量限制(不超过100100)。如果是高级装备,后面紧跟着一个正整数CC,表示这个高级装备需要CC种低级装备。后面的2C2C个数,依次描述某个低级装备的种类和需要的个数。

Output

第一行包含一个整数SS,表示最多可以提升多少点力量值。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
10 59
5 A 3 6 1 9 2 10 1
1 B 5 3
1 B 4 3
1 B 2 3
8 A 3 2 1 3 1 7 1
1 B 5 3
5 B 3 3
15 A 3 1 1 5 1 4 1
1 B 3 5
1 B 4 3

Sample Output

1
33

Solution

枚举装备xx买了numnum个。
fx,i,jf_{x,i,j}表示装备xx,买了numnum个,多买了ii个用于上级合成,共在其子树内花了jj元得到的最大力量。
gx,i,jg_{x,i,j}表示装备xx,买了numnum个,到ii个装备为止(可以滚掉),共花了jj元得到的最大力量。
fx,i,j=max{g[x][tot][k]+(numi)×v[x]}f_{x,i,j}=\max\{g[x][tot][k] + (num - i)\times v[x]\}
gx,i,j=max{gx,i1,jk+fy,num×e[T].w,k}g_{x,i,j}=\max\{g_{x,i-1,j-k}+f_{y,num\times e[T].w,k}\}

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 55, M = 21000;
int n, m;
int type[N], v[N], lim[N], w[N];
char op[5];
struct Edge {
int u, v, nxt, w;
}e[M];
int head[N], en, ind[N];
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].w = z;
++ind[y];
}
int f[N][120][2100];
int g[2][2200];
void dfs(int x) {
if(!head[x]) {
if(w[x])lim[x] = min(lim[x], m / w[x]);
for(int num = 0; num <= lim[x]; ++num) {
for(int i = 0; i <= num; ++i)
f[x][i][num * w[x]] = v[x] * (num - i);
}
return ;
}
lim[x] = 1e9;
for(int i = head[x]; i;i = e[i].nxt) {
dfs(e[i].v);
w[x] += w[e[i].v] * e[i].w;
lim[x] = min(lim[x], lim[e[i].v] / e[i].w);
}
lim[x] = min(lim[x], m / w[x]);
for(int num = 0; num <= lim[x]; ++num) {
int t = 0;
memset(g[t],-0x3f,sizeof g[t]);
g[t][0] = 0;
for(int T = head[x]; T;T = e[T].nxt) {
int y = e[T].v;
t ^= 1;
memset(g[t],-0x3f,sizeof g[t]);
for(int j = 0; j <= m; ++j) {
for(int k = 0; k <= j; ++k)
g[t][j] = max(g[t][j], g[t ^ 1][j - k] + f[y][num * e[T].w][k]);
}
}
for(int i = 0; i <= num; ++i)
for(int j = 0; j <= m; ++j)
f[x][i][j] = max(f[x][i][j], g[t][j] + (num - i) * v[x]);
}
}
int ans[2100];
int main() {
memset(f,-0x3f,sizeof f);
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
v[i] = read();
scanf("%s", op);
if(op[0] == 'A') {
int t = read();
for(int j = 1; j <= t; ++j) {
int x = read();
int y = read();
addedge(i, x, y);
}
} else w[i] = read(), lim[i] = read();
}
for(int i = 1; i <= n; ++i) if(!ind[i]) {
dfs(i);
for(int j = m; ~j; --j)
for(int k = 0; k <= j; ++k) {
ans[j] = max(ans[j], ans[j - k] + f[i][0][k]);
}
}
writeln(ans[m]);
return 0;
}