[JSOI2008]魔兽地图

标签： 动态规划 树形结构 树形DP

---

题目描述

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（幽灵附体）作为回报的。

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例#1：
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
输出样例#1：
33

题解

此题很明显是一个tree dp。但是看出来也没什么用，主要是状态转移真的不好想。
很容易想到这样一个转移方程:dp[i][j][k]表示以i为根，第i个节点购买j件，共分配k元给它所得到的最大收益。
但一转移就出锅了（其实当时我还是坚信这个方程是对的…直到调出shit来以后才意识到有什么不对）
为什么这样转移会出问题呢，其实主要是我们不知道他到底会有几件是用作合成的。就是儿子与父亲是有联系的，或者说儿子决定了父亲（因为有合成的限制嘛）
所以需要抄题解换一个角度设计方程:dp[i][j][k]表示以i为根，第i个节点共有j件用于合成，共分配k元给它所得到的最大收益。
你看这样设计方程，便得到了儿子与父亲的联系。（其实状态中我们不用关注儿子到底购买了几件，因为除了合成购买件数所花费的钱以外剩下的钱它想干啥干啥，只要收益最大就可以了）
我们首先最外层枚举一个l表示当前节点要合成l件。
为了转移方便，我们还需要一个g[tot][j]表示前tot个儿子分配j元并且满足此时父亲所需要件数（l * need[son]件）所得到的最大收益。
然后先转移g，就可以得到任意金币数下得到的最大收益。
最后再通过g再来转移f。
需要注意的是，最后可能是一个森林，所以最后还要做一个泛化背包

代码

#include<bits/stdc++.h>
#define N 60
#define M 2010
#define debug system("pause")
using namespace std;

char cc, c[N];
int n, m, p, x, y, k = 0;
int num[N], v[N], w[N], ans[M], head[N];
int g[N][M], dp[N][M], d[N][N], f[N][N * 2][M];
bool vis[N];
struct node{int to, next;}e[N * 2];

void add(int u, int v)
{
    e[++ k].next = head[u]; e[k].to = v;
    head[u] = k;
}

void dfs(int x)
{
    if(!head[x])
    {
       for(int i = 0; i <= num[x]; i ++)
           for(int j = i; j <= num[x]; j ++)
               f[x][i][j * v[x]] = (j - i) * w[x];
        return;
    }
    int max_num = 1e9;
    for(int i = head[x]; i; i = e[i].next)
    {
        dfs(e[i].to);
        max_num = min(max_num, num[e[i].to] / d[x][e[i].to]);
        v[x] += v[e[i].to] * d[x][e[i].to];
    }
    num[x] = min(max_num, m / v[x]);
    for(int l = 0; l <= num[x]; l ++) 
    {
        memset(g, -0x3f3f3f, sizeof(g)); //这里需要初始化，否则倒序枚举l 
        g[0][0] = 0;
        int tot = 0;
        for(int i = head[x]; i; i = e[i].next)
        {
            int to = e[i].to; tot ++;
            for(int j = m; j >= 0; j --)
                for(int k = 0; k <= j; k ++)
                    g[tot][j] = max(g[tot][j], g[tot - 1][k] + f[to][l * d[x][to]][j - k]);
        }
        for(int i = 0; i <= l; i ++)
            for(int j = m; j >= 0; j --)
                f[x][i][j] = max(f[x][i][j], g[tot][j] + (l - i) * w[x]);
    }    
}

int main()
{
    memset(f, -0x3f3f3f, sizeof(f));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d%c%c", &w[i], &cc, &c[i]);
        if(c[i] == 'A')
        {
            scanf("%d", &p);
            for(int j = 1; j <= p; j ++) 
            {
                scanf("%d%d", &x, &y);
                d[i][x] = y; add(i, x);
                vis[x] = true;
            }
        }
        else 
        {
            scanf("%d%d", &v[i], &num[i]);
            num[i] = min(num[i], m / v[i]);
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; i ++)
        if(!vis[i]) 
        {
            dfs(i); cnt ++;
            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]);
        }
    printf("%d", ans[m]);
    return 0;
}

心得

感觉tree dp有时候不按套路来啊，还是需要具体问题具体分析，找到题目的性质才是重要的。