P4037 [JSOI2008] 魔兽地图 题解

· · 题解

非常好的一道树上背包。

先分析题目。我们发现对于一种装备，它要么不升级，用自己来贡献答案；要么升级，获取高阶装备的贡献。因此普通树上背包的状态不够转移，考虑多添加一位。因此我们用 dp_{u,i,j} v表示在 u 的子树中，u 会向他的父节点提供 i 个自己，同时 u 子树内的花费为 j 时的最大力量值。

首先考虑叶子节点的初始化。对于每个叶子节点的装备，我们枚举其选了多少个（用 i 表示），然后枚举它向父亲贡献的个数（j）。此时它的贡献即为 p_{leaf} \times (i - j)。

然后考虑转移。最外层枚举合成了多少个该物品（i），然后每次统计在 i 的情况下对于每个花费的值。对于一个花费 j，g_j = g_{j - k} + dp_{son,i \times w,k}，其中 k 表示当前子树的枚举花费值。由于要选 i 个此物品，那么它的每个子节点都必须向它提供合成材料，即 i \times w，其中 w 表示兑换比值。然后把 g 里临时存放的转移的值并到 dp 上。

需要注意，此题可能是个森林，因此在外面还要做一次背包。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 52;
const int M = 2005;
const int inf = 1e9;
struct edges{
    int to, next, w;
};
edges edge[N << 1];
int n, m, cnt = 0;
int p[N], cost[N], lim[N], in[N], head[N], g[M], dp[N][2 * N][M], ans[M];

void add_edge(int u, int v, int w){
    edge[++ cnt].to = v;
    edge[cnt].next = head[u];
    edge[cnt].w = w;
    head[u] = cnt;
}
void dfs(int u){
    if(! head[u]){
        lim[u] = min(lim[u], m / cost[u]);
        for(int i = 0; i <= lim[u]; i ++)
          for(int j = 0; j <= i; j ++)
            dp[u][j][i * cost[u]] = p[u] * (i - j);
        return;
    }
    lim[u] = inf; cost[u] = 0;
    for(int i = head[u]; i; i = edge[i].next){
        int v = edge[i].to, w = edge[i].w;
        dfs(v);
        cost[u] += cost[v] * w;
        lim[u] = min(lim[u], lim[v] / w);
    }
    lim[u] = min(lim[u], m / cost[u]);
    for(int i = lim[u]; i >= 0; i --){
        memset(g, -0x3f, sizeof g); g[0] = 0;
        for(int ii = head[u]; ii; ii = edge[ii].next){
          int v = edge[ii].to, w = edge[ii].w;
            for(int j = m; j >= 0; j --){
              int tmp = -inf;
              for(int k = 0; k <= j; k ++)
                tmp = max(tmp, g[j - k] + dp[v][i * w][k]);
              g[j] = tmp;
            }
        }
        for(int j = 0; j <= i; j ++)
          for(int k = 0; k <= m; k ++)
            dp[u][j][k] = max(dp[u][j][k], g[k] + (i - j) * p[u]);
    }
}
int main(){
    memset(dp, -0x3f, sizeof dp);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &p[i]);
        char c; cin >> c;
        if(c == 'A'){
            int cs; scanf("%d", &cs);
            for(int j = 1; j <= cs; j ++){
                int v, w; scanf("%d %d", &v, &w);
                add_edge(i, v, w);
                in[v] ++;
            }
        }else scanf("%d %d", &cost[i], &lim[i]);
    }
    for(int i = 1; i <= n; i ++){
        if(in[i]) continue;
        dfs(i);
        for(int j = m; j >= 0; j --)
          for(int k = 0; k <= j; k ++) ans[j] = max(ans[j], ans[j - k] + dp[i][0][k]);
    }
    printf("%d\n", ans[m]);
    return 0;
}