TopCoder SRM 666 Div2 Problem 999 - WalkOverATreeDiv2 (树形DP)

## 题意 ##

一棵树，每个结点有权，现在从1开始最多走L步，问最多能收获多少。

## 思路 ##

树形DP。

dp(u, step, 0)表示u结点走step步后不回到u结点的最大值。dp(u, step, 1)是回到u。

现在考虑转移。显然dp(u, step, 1) = max(dp(child, step-2-cur_step, 1))。-2是因为走到孩子结点再走回来要两步。

现在考虑dp(u, step, 0)。有两种可能，一种是停在当前孩子结点下面，另一种是当前孩子结点走完，停在另外的孩子结点下面。

具体的http://blog.csdn.net/lishuandao/article/details/48010589 这位巨巨已经说得很清楚了。

class CollectingTokens {
public:
 
    int dp[MAXN][110][2], tmp[110][2], lim, w[MAXN];
    vector<int> G[MAXN];
 
    void update(int &u, int v)
    {
        u = max(u, v);
    }
 
    void dfs(int u, int fa)
    {
        dp[u][0][0] = dp[u][0][1] = w[u];
        for (int i = 0; i < SZ(G[u]); i++)
        {
            int v = G[u][i];
            if (v == fa) continue;
            dfs(v, u);
            for (int j = 0; j <= lim; j++) tmp[j][0] = tmp[j][1] = -INF;
            for (int step = 1; step <= lim; step++)
            {
                for (int cur = step; cur >= 0; cur--)    //1回来
                {
                    if (step-cur-1 >= 0) update(tmp[step][0], dp[u][step-cur-1][1] + dp[v][cur][0]);
                    if (step-cur-2 >= 0)
                    {
                        update(tmp[step][0], dp[u][step-cur-2][0] + dp[v][cur][1]);
                        update(tmp[step][1], dp[u][step-cur-2][1] + dp[v][cur][1]);
                    }
                }
            }
            for (int j = 1; j <= lim; j++)
            {
                update(dp[u][j][0], tmp[j][0]);
                update(dp[u][j][1], tmp[j][1]);
            }
        }
    }
 
    int maxTokens(vector<int> A, vector<int> B, vector<int> tokens, int L) {
        for (int i = 0; i < SZ(A); i++)
        {
            G[A[i]].PB(B[i]);
            G[B[i]].PB(A[i]);
        }
        lim = L;
        for (int i = 0; i < SZ(tokens); i++) w[i+1] = tokens[i];
        dfs(1, -1);
        int ans = 0;
        for (int i = 0; i <= L; i++) update(ans, max(dp[1][i][0], dp[1][i][1]));
        return ans;
    }
};

Published on Aug 31, 2015 in categories Solving-Reports