HDU 1011 Starship Troopers （树形DP+依赖背包）

dp[i][j]: 以i为根的子树花费为j时的最大收益。

dp[i][j] = max(dp[i][j],dp[i][j-k] + dp[son(i)][k])

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 111;
int n,m;
vector<int> son[maxn];
int bugs[maxn],val[maxn],cost[maxn];
bool vis[maxn];
int dp[maxn][maxn];

void dfs(int u)
{
    vis[u] = true;
    for (int i = cost[u]; i <= m; ++i)
        dp[u][i] = val[u];
    int size = son[u].size();
    
    for (int i = 0; i < size; ++i)
    {
        int v = son[u][i];
        if (vis[v]) continue;
        dfs(v);
        for (int j = m; j >= cost[u]; --j)
        {
            // k要从1开始 
            for (int k = 1; k + cost[u] <= j; ++k)
                dp[u][j] = max(dp[u][j],dp[u][j-k] + dp[v][k]);
        }
    }
}

int main()
{
    while (scanf("%d %d",&n,&m))
    {
        if (n == -1 && m == -1)
            break;
        
        int a,b;
        for (int i = 0; i < maxn; ++i)
            son[i].clear();
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d %d",&bugs[i],&val[i]);
        }
        for (int i = 1; i <= n; ++i)
            cost[i] = (bugs[i] + 19) / 20;
        for (int i = 1; i < n; ++i)
        {
            scanf("%d %d",&a,&b);
            son[a].push_back(b);
            son[b].push_back(a);
        }
        memset(vis,false,sizeof(vis));
        memset(dp,sizeof(dp));
        
        if(m == 0) // 这个判断要有 
        {
            printf("0n");
            continue;
        }
        dfs(1);
        printf("%dn",dp[1][m]);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!