[JSOI2008] 魔兽地图

GitHub跳转原题关系图返回列表

把装备合成关系看成森林，设 f[u][j][c] 表示在 u 的子树里留出 j 个 u 给父亲继续合成、花费 c 金币时能得到的最大力量值，再做树形分组背包合并子树。

OJ: luogu

题目 ID: P4037

难度:提高+/省选-

标签:动态规划树形DP背包状态设计

日期: 2026-06-21 10:35

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

有两类装备：

  • 基本装备：可以直接花金币购买，且有数量限制
  • 高级装备：由若干低级装备合成，合成不额外花金币

每件装备都有固定的力量值。
英雄有 M 金币，目标是在预算内让总力量值尽量大。

题目保证装备的合成关系是一片森林。

思路

先看一个可以直接验证想法的小数据版本：

cpp
#include <bits/stdc++.h>
using namespace std;

const int NEG_INF = -1000000000;

struct NodeInfo {
    int power;
    char type;
    int cost;
    int limit;
    vector<pair<int, int> > child;
};

int n, m;
NodeInfo nodes[55];
int indeg[55];
int max_make[55];
int min_cost[55];
vector<vector<int> > dp_node[55];
int ans[2005];

void solve(int u) {
    if (!dp_node[u].empty()) {
        return;
    }

    if (nodes[u].type == 'B') {
        max_make[u] = min(nodes[u].limit, m / nodes[u].cost);
        min_cost[u] = nodes[u].cost;
        dp_node[u].assign(max_make[u] + 1, vector<int>(m + 1, NEG_INF));

        for (int reserved = 0; reserved <= max_make[u]; reserved++) {
            for (int total = reserved; total <= max_make[u]; total++) {
                int cost = total * nodes[u].cost;
                dp_node[u][reserved][cost] = nodes[u].power * (total - reserved);
            }
        }
        return;
    }

    max_make[u] = 1000000000;
    min_cost[u] = 0;
    for (size_t i = 0; i < nodes[u].child.size(); i++) {
        int v = nodes[u].child[i].first;
        int need = nodes[u].child[i].second;
        solve(v);
        max_make[u] = min(max_make[u], max_make[v] / need);
        min_cost[u] += need * min_cost[v];
    }
    max_make[u] = min(max_make[u], m / min_cost[u]);

    dp_node[u].assign(max_make[u] + 1, vector<int>(m + 1, NEG_INF));

    for (int total = 0; total <= max_make[u]; total++) {
        vector<int> cur(m + 1, NEG_INF);
        cur[0] = 0;

        for (size_t i = 0; i < nodes[u].child.size(); i++) {
            int v = nodes[u].child[i].first;
            int need = nodes[u].child[i].second;
            vector<int> nxt(m + 1, NEG_INF);
            for (int c1 = 0; c1 <= m; c1++) {
                if (cur[c1] == NEG_INF) {
                    continue;
                }
                for (int c2 = 0; c1 + c2 <= m; c2++) {
                    if (dp_node[v][total * need][c2] == NEG_INF) {
                        continue;
                    }
                    nxt[c1 + c2] = max(nxt[c1 + c2], cur[c1] + dp_node[v][total * need][c2]);
                }
            }
            cur.swap(nxt);
        }

        for (int reserved = 0; reserved <= total; reserved++) {
            for (int cost = 0; cost <= m; cost++) {
                if (cur[cost] == NEG_INF) {
                    continue;
                }
                dp_node[u][reserved][cost] =
                    max(dp_node[u][reserved][cost], cur[cost] + nodes[u].power * (total - reserved));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据精确 DP，用来帮助理解并辅助对拍。
    // 仍按题目的合成树定义做状态，但不做任何额外优化。
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> nodes[i].power >> nodes[i].type;
        if (nodes[i].type == 'A') {
            int c;
            cin >> c;
            nodes[i].child.resize(c);
            for (int j = 0; j < c; j++) {
                int x, y;
                cin >> x >> y;
                nodes[i].child[j] = make_pair(x, y);
                indeg[x]++;
            }
        } else {
            cin >> nodes[i].cost >> nodes[i].limit;
        }
    }

    for (int i = 0; i <= m; i++) {
        ans[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            solve(i);
            for (int cost = m; cost >= 0; cost--) {
                for (int used = 0; used <= cost; used++) {
                    if (dp_node[i][0][used] == NEG_INF) {
                        continue;
                    }
                    ans[cost] = max(ans[cost], ans[cost - used] + dp_node[i][0][used]);
                }
            }
        }
    }

    cout << ans[m] << '\n';
    return 0;
}

这题的关键在于：

一个子树不仅会给自己贡献力量值，还可能要“留出若干件当前装备”给父亲继续合成。

所以设：

f[u][j][c]

表示在 u 这棵子树里：

  • 留出 j 件 u 给父亲继续合成
  • 花费 c 金币
  • 能得到的最大力量值

DP 转移方程

基本装备的状态来自“买 t 件，留 j 件”：

f[u][j][cost]=(t−j)⋅value[u] f[u][j][cost] = (t-j)\cdot value[u]

高级装备先枚举合成 i 件，再把每个儿子的需求做分组背包合并。 如果儿子 v 需要提供 need 件，则合并金币维度时本质是：

tmp[c1+c2]=max⁡(tmp[c1+c2], cur[c1]+f[v][need][c2]) tmp[c_1+c_2]=\max(tmp[c_1+c_2],\ cur[c_1]+f[v][need][c_2])

合成出的 i 件中留下 j 件给父亲，剩余 i-j 件计入当前装备价值。

对于基本装备很好理解：

  • 如果总共买了 t 件
  • 其中 j 件留给父亲
  • 那么剩下 t-j 件可以直接贡献力量值

对于高级装备：

  1. 先假设总共要合成 i 件当前装备
  2. 那么每个儿子都必须提供固定数量的子装备
  3. 儿子之间做一次分组背包，求出满足这些原料需求时的最优力量值
  4. 再枚举其中有多少件 j 要留给父亲，剩下 i-j 件自己计入力量值

最后因为整张图可能是一片森林，再把所有根节点做一次总背包合并即可。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int MAXK = 105;
const int MAXM = 2005;
const int NEG_INF = -1000000000;

struct Edge {
    int to, need, next;
} edges[MAXN * MAXN];

int n, m;
int edge_cnt;
int head[MAXN];
int indeg[MAXN];

int power_val[MAXN];
int buy_cost[MAXN];
int limit_cnt[MAXN];
int min_cost[MAXN];
int vis[MAXN];

int f[MAXN][MAXK][MAXM];
int g[MAXM];
int ans[MAXM];

void add_edge(int u, int v, int w) {
    edge_cnt++;
    edges[edge_cnt].to = v;
    edges[edge_cnt].need = w;
    edges[edge_cnt].next = head[u];
    head[u] = edge_cnt;
    indeg[v]++;
}

void solve(int u) {
    if (vis[u]) {
        return;
    }
    vis[u] = 1;

    if (head[u] == 0) {
        limit_cnt[u] = min(limit_cnt[u], m / buy_cost[u]);
        for (int reserved = limit_cnt[u]; reserved >= 0; reserved--) {
            for (int total = reserved; total <= limit_cnt[u]; total++) {
                int cost = total * buy_cost[u];
                f[u][reserved][cost] = power_val[u] * (total - reserved);
            }
        }
        return;
    }

    limit_cnt[u] = 1000000000;
    min_cost[u] = 0;

    for (int e = head[u]; e != 0; e = edges[e].next) {
        int v = edges[e].to;
        solve(v);
        limit_cnt[u] = min(limit_cnt[u], limit_cnt[v] / edges[e].need);
        min_cost[u] += edges[e].need * min_cost[v];
    }

    limit_cnt[u] = min(limit_cnt[u], m / min_cost[u]);

    for (int total = limit_cnt[u]; total >= 0; total--) {
        for (int cost = 0; cost <= m; cost++) {
            g[cost] = NEG_INF;
        }
        g[0] = 0;

        for (int e = head[u]; e != 0; e = edges[e].next) {
            int v = edges[e].to;
            for (int cost = m; cost >= 0; cost--) {
                int best = NEG_INF;
                for (int used = 0; used <= cost; used++) {
                    if (g[cost - used] == NEG_INF || f[v][total * edges[e].need][used] == NEG_INF) {
                        continue;
                    }
                    best = max(best, g[cost - used] + f[v][total * edges[e].need][used]);
                }
                g[cost] = best;
            }
        }

        for (int reserved = 0; reserved <= total; reserved++) {
            for (int cost = 0; cost <= m; cost++) {
                if (g[cost] == NEG_INF) {
                    continue;
                }
                f[u][reserved][cost] =
                    max(f[u][reserved][cost], g[cost] + power_val[u] * (total - reserved));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(f, 0xc0, sizeof(f));

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> power_val[i];
        char type;
        cin >> type;
        if (type == 'A') {
            int c;
            cin >> c;
            for (int j = 1; j <= c; j++) {
                int x, y;
                cin >> x >> y;
                add_edge(i, x, y);
            }
        } else {
            cin >> buy_cost[i] >> limit_cnt[i];
            min_cost[i] = buy_cost[i];
        }
    }

    for (int i = 0; i <= m; i++) {
        ans[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            solve(i);
            for (int cost = m; cost >= 0; cost--) {
                for (int used = 0; used <= cost; used++) {
                    if (f[i][0][used] == NEG_INF) {
                        continue;
                    }
                    ans[cost] = max(ans[cost], ans[cost - used] + f[i][0][used]);
                }
            }
        }
    }

    cout << ans[m] << '\n';
    return 0;
}

复杂度

设金币上限为 M。

这份做法的复杂度大致是树形分组背包级别，核心复杂度约为 O(节点数∗件数上限∗M2)O(节点数 * 件数上限 * M^2)。

在本题给定的官方范围下，这也是目前常见题解采用的主流模型。

总结

这题最容易漏掉的一点是：

子树不是只回答“我自己能做多少价值”，还要回答“我还能向父亲提供多少件当前装备”。

把这一维状态补进去之后，整道题就变成标准的树形背包。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析