给定 $n$ 件物品， $m$ 个金币，每个物品有自己的价值。低级物品可以直接购买，高级物品需要若干件较低级的物品来合成，并且具有合成的数量限制，求能够获得的最大价值。

题解

很不错的树形DP，反正我一开始是没想出来。

设 $p_i, c_i, w_i$ 分别表示物品 $i$ 的价值，合成数量限制和价格。

高级装备的 $w, c$ 用子树的信息合并一下就好。

设 $f(i, j, k)$ 为合成 $j$ 件物品 $i$ 贡献给父节点，花费了 $k$ 个金币所能获得的最大价值。记 $son_i$ 为节点 $i$ 的子节点集合。

枚举合成 $a$ 件 $i$ 物品，余下的钱用来购买一些子树中的物品来获得价值。

对于枚举到的合成数目 $a$ ，设 $g(t, j)$ 表示在某个节点的前 $t$ 棵子树花费 $j$ 个金币所能获得的最大收益， $q_i(k)$ 表示合成物品 $i$ 所需物品 $k$ 的数量。

g(t, j) = \max\limits_{k = 0}^{j}\{g(t, j), g(t - 1, j - k) + f(son_i(t), a \times q_i(son_i(t)), j)\}

从合成的 $a$ 件中挑选 $j$ 件贡献给父节点，由此转移 $f(i, j, k)$ 。

f(i, j, k) = \max\{ g(|son_i|, k) + p_i \times (a - j) \}

这道题最巧妙的决策点在确定合成一件物品时用来获得价值的数目和拿来合成更高级物品的数目。

然后，如果没有任何高级装备的话，需要另写一个多重背包来特判。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <algorithm>
const int MAX_N = 51;
const int MAX_M = 2000;
const int MAX_K = 100;
int n, m;
struct Node;
struct Edge;
struct Node {
    Edge *e;
    int cnt, cost, p, d;
    int f[MAX_K + 1][MAX_M + 1];
    bool basic;
} N[MAX_N + 1];
struct Edge {
    Node *fr, *to;
    Edge *ne;
    int w;
    Edge(Node *fr, Node *to, int w) : fr(fr), to(to), ne(fr->e), w(w) {}
};
inline void addEdge(int fr, int to, int w) {
    N[to].d++;
    N[fr].e = new Edge(&N[fr], &N[to], w);
}
int g[MAX_N + 1][MAX_M + 1], h[MAX_N + 1][MAX_M + 1];
inline void dp(Node *v) {
    int (&f)[MAX_K + 1][MAX_M + 1] = v->f;
    
    if (v->basic) {
        v->cnt = std::min(v->cnt, m / v->cost);
        for (int i = 0; i <= v->cnt; i++)
            for (int j = i; j <= v->cnt; j++)
                f[i][j * v->cost] = (j - i) * v->p;
        return;
    } else {
        v->cnt = INT_MAX;
        for (Edge *e = v->e; e; e = e->ne) {
            dp(e->to);
            v->cnt = std::min(v->cnt, e->to->cnt / e->w);
            v->cost += e->w * e->to->cost;
        }
        v->cnt = std::min(v->cnt, m / v->cost);
        memset(g, -0x3f3f3f3f, sizeof(g));
        g[0][0] = 0;
        for (int a = v->cnt; a >= 0; a--) {
            int id = 0;
            for (Edge *e = v->e; e; e = e->ne) {
                id++;
                for (int j = 0; j <= m; j++)
                    for (int k = 0; k <= j; k++)
                        g[id][j] = std::max(g[id][j], g[id - 1][j - k] + e->to->f[e->w * a][k]);
            }
            for (int i = 0; i <= a; i++)
                for (int k = 0; k <= m; k++)
                    f[i][k] = std::max(f[i][k], g[id][k] + v->p * (a - i));
        }
    }
}
inline void solveTree() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= MAX_K; j++)
            for (int k = 0; k <= MAX_M; k++)
                N[i].f[j][k] = -100000000;
    }
    int tot = 0;
    for (int x = 1; x <= n; x++) {
        Node *v = &N[x];
        if (!v->d) {
            dp(v);
            tot++;
            for (int i = 0; i <= m; i++)
                for (int j = 0; j <= i; j++)
                    for (int k = 0; k <= v->cnt; k++)
                        h[tot][i] = std::max(h[tot][i], h[tot - 1][j] + v->f[k][i - j]);
        }
    }
    int ans = INT_MIN;
    for (int j = 0; j <= m; j++) ans = std::max(ans, h[tot][j]);
    printf("%d\n", ans);
}
template<class T>
struct MonoQueue {
    std::deque<T> data, aux;
    void push(const T &x) {
        data.push_back(x);
        while (!aux.empty() && aux.back() < x) aux.pop_back();
        aux.push_back(x);
    }
    void pop() {
        if (data.front() == aux.front()) aux.pop_front();
        data.pop_front();
    }
    int size() {
        return data.size();
    }
    T max() {
        return aux.front();
    }
};
int f[MAX_M + 1];
inline void multiplePack(int cost, int w, int cnt) {
    cnt = std::min(cnt, m / cost);
    for (int d = 0; d < cost; d++) {
        MonoQueue<int> q;
        for (int k = 0; k * cost + d <= m; k++) {
            q.push(f[k * cost + d] - k * w);
            if (q.size() == cnt + 2) q.pop();
            f[k * cost + d] = q.max() + k * w;
        }
    }
}
inline void solveMultiplePack() {
    for (int i = 1; i <= n; i++) {
        multiplePack(N[i].cost, N[i].p, N[i].cnt);
    }
    int ans = INT_MIN;
    for (int i = 0; i <= m; i++) {
        ans = std::max(ans, f[i]);
    }
    printf("%d\n", ans);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &N[i].p);
        char ch[5];
        scanf("%s", ch);
        if (ch[0] == 'B') {
            scanf("%d %d", &N[i].cost, &N[i].cnt);
            N[i].basic = true;
        } else {
            int c;
            scanf("%d", &c);
            while (c--) {
                int v, w;
                scanf("%d %d", &v, &w);
                addEdge(i, v, w);
            }
        }
    }
    bool flag = false;
    for (int i = 1; i <= n; i++) if (N[i].d) flag = true;
    if (flag) solveTree();
    else solveMultiplePack();
    return 0;
}

「JSOI2008」魔兽地图 - 树形DP，多重背包

Contents

题解

代码