1017: [JSOI2008]魔兽地图DotR
Time Limit: 30 Sec Memory Limit: 162 MBDescription
DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA
(Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的
力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力
量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本
装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如，Sange
and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt
of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无限制地合成某
些性价比很高的装备。现在，英雄Spectre有M个金币，他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他
吗？他会教你魔法Haunt（幽灵附体）作为回报的。
Input
第一行包含两个整数，N (1 <= n <= 51) 和 m (0 <= m <= 2,000)。分别表示装备的种类数和金币数。装备
用1到N的整数编号。接下来的N行，按照装备1到装备n的顺序，每行描述一种装备。每一行的第一个非负整数表示这
个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备，A表示高级装备，B表示基本装备
。如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过100）。如果是高
级装备，后面紧跟着一个正整数C，表示这个高级装备需要C种低级装备。后面的2C个数，依次描述某个低级装备的
种类和需要的个数。
Output
第一行包含一个整数S，表示最多可以提升多少点力量值。
Sample Input
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
好神的dp!
因为装备的合成路线是一棵树，所以我们可以套用树形dp.
我们设状态 f[i][j][k] 表示 到了第i个装备有j个用于向上合成一共花费k元能得到的最大力量
转移时我们枚举每个装备的购买数量L
g[i][j] 表示到第i个儿子花了j元的最大力量
g[i][j]可以用背包转移
f[i][j][k] = g[last son][k] + (L - j) * p[i];
然而复杂度很玄学，要加一个剪枝
v[i] 是装备合成的总价格, l[i] 表示i的最大上限
l[i] = min(l[son] / 合成所需， M / v[i]);
于是就过了。。。
?1 #include <iostream> ?2 #include <cstdio> ?3 #include <cstring> ?4 #include <cstdlib> ??5 #include <algorithm> ?6 #define LL long long ?7 ??8 using namespace std; ?9 ?10 const int MAXN = 100, MAXM = 3000; 11 int N, M; 12 int cnt = 0; 13 int ans[MAXN][MAXM]; 14 int maxn; 15 int head[MAXN]; 16 int p[MAXN]; 17 int v[MAXN]; 18 int l[MAXN]; 19 int in[MAXN]; 20 int f[MAXN][MAXN][MAXM]; 21 int gg[MAXN][MAXM]; 22 ?23 struct edge { 24 ????int need; 25 ????int v; 26 ????int next; 27 } g[MAXM * 2]; 28 char kind[100][10]; 29 ?30 void addedge(int u, int v, int w) 31 { 32 ????g[++cnt].v = v; 33 ????g[cnt].next = head[u]; 34 ????g[cnt].need = w; 35 ????head[u] = cnt; 36 } 37 inline LL read() 38 { 39 ????LL x = 0, w = 1; char ch = 0; 40 ????while(ch < ‘0‘ || ch > ‘9‘) { 41 ????????if(ch == ‘-‘) { 42 ????????????w = -1; 43 ????????} 44 ????????ch = getchar(); 45 ????} 46 ????while(ch >= ‘0‘ && ch <= ‘9‘) { 47 ????????x = x * 10 + ch - ‘0‘; 48 ????????ch = getchar(); 49 ????} 50 ????return x * w; 51 } 52 ?53 void DFS(int x) 54 { 55 ????if(kind[x][0] == ‘A‘) { 56 ????????l[x] = MAXN; 57 ????????for(int j = head[x]; j; j = g[j].next) { 58 ????????????int to = g[j].v; 59 ????????????DFS(to); 60 ????????????v[x] += v[to] * g[j].need; 61 ????????????l[x] = min(l[x], l[to] / g[j].need); 62 ????????} 63 ????????l[x] = min(l[x], M / v[x]); 64 ????????for(int L = l[x]; L >= 0; L--) { // 枚举x装备购买数量 ?65 ????????????int tot = 0; 66 ????????????memset(gg, -0x3f3f3f3f, sizeof gg); 67 ???????????????gg[0][0] = 0; 68 ????????????for(int j = head[x]; j; j = g[j].next) { 69 ????????????????++tot; 70 ????????????????int to = g[j].v; 71 ????????????????for(int m = 0; m <= M; m++) { 72 ????????????????????for(int k = 0; k <= m; k++) { 73 ????????????????????????gg[tot][m] = max(gg[tot][m], gg[tot - 1][k] + f[to][L * g[j].need][m - k]); ?74 ????????????????????} 75 ????????????????} 76 ????????????} 77 ????????????for(int k = 0; k <= M; k++) { 78 ????????????????for(int j = 0; j <= L; j++) { 79 ????????????????????f[x][j][k] = max(f[x][j][k], gg[tot][k] + (L - j) * p[x]); 80 ????????????????} 81 ????????????} 82 ????????} 83 ????} else { 84 ????????for(int L = 0; L <= min(M / v[x], l[x]); L++) { 85 ????????????for(int j = 0; j <= L; j++) { 86 ????????????????f[x][j][v[x] * L] = (L - j) * p[x]; 87 ????????????} 88 ????????} 89 ????} 90 } 91 int main() 92 { 93 // ???freopen("t.out", "w", stdout); 94 ????memset(f, -0x3f3f3f3f, sizeof f); 95 ????N = read(), M = read(); 96 ????for(int i = 1; i <= N; i++) { 97 ????????p[i] = read(); 98 ????????scanf("%s", kind[i]); 99 ????????if(kind[i][0] == ‘A‘) {100 ????????????int C = read();101 ????????????for(int j = 1; j <= C; j++) {102 ????????????????int v = read(), w = read();103 ????????????????in[v]++;104 ????????????????addedge(i, v, w);105 ????????????}106 ????????} else {107 ????????????v[i] = read(), l[i] = read();108 ????????}109 ????}110 ????int tot = 0;111 ????for(int i = 1; i <= N; i++) {112 ????????if(!in[i]) {113 ????????????++tot;114 ????????????DFS(i);115 ????????????for(int j = 0; j <= M; j++) {116 ????????????????for(int k = 0; k <= j; k++) {117 ????????????????????//for(int t = 0; t <= l[t]; t++) {118 ????????????????????????ans[tot][j] = max(ans[tot][j], ans[tot - 1][k] + f[i][0][j - k]);119 ????????????????????//}120 ????????????????}121 ????????????}122 ????????}123 ????}124 ????for(int i = 0; i <= M; i++) {125 ????????maxn = max(ans[tot][i], maxn);126 ????}127 ????printf("%d\n", maxn);128 ????return 0;129 }130 131 /*132 133 10 59134 5 A 3 6 1 9 2 10 1135 1 B 5 3136 1 B 4 3137 1 B 2 3138 8 A 3 2 1 3 1 7 1139 1 B 5 3140 5 B 3 3141 15 A 3 1 1 5 1 4 1142 1 B 3 5143 1 B 4 3144 145 */bzoj 1017[JSOI2008]魔兽地图DotR - 树形dp
原文地址：https://www.cnblogs.com/wuenze/p/8438196.html