hdu 4276 树形DP + 分组背包

题意：一棵树，让你在规定时间Ｔ内从１号节点走到ｎ号节点，并取得最多的宝藏值。
很容易可以想到一个这样子的树形DP，dp[u][t]表示u子树走t长度的距离时所能获得的最大价值，然后就是1 到 n的链上的每个点来分配容量为T的背包
其实就是一个分组背包了，链上的每个点代表每一组，每组中的物品为求得的状态dp[u][0->t]，每组至少取一个物品
还有一个注意点就是边权有可能为0，所以在树形DP转移的过程中要注意了。
以后还是尽量用tmp变量转移吧，保险- -
[cpp]
#include<cstdio>
#include<cstring>
#include<set>
#include<string>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<time.h>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 110;
#define lowbit(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define PB push_back
#define MP make_pair
typedef unsigned long long ULL;
typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int,int> PII;
vector<PII> edge[maxn];
int n,T;
int val[maxn];
int pre[maxn];
bool flag[maxn];
void dfs1(int u,int f)
{
    if(u==n)
    {
        pre[u]=f;
        return ;
    }
    for(int i=0;i<edge[u].size();i++)
    {
        int v=edge[u][i].first;
        if(v==f) continue;
        pre[v]=u;
        dfs1(v,u);
    }
}
int dp[maxn][510];
void Max(int &a,int cmp){
    if(cmp>a) a=cmp;
}
void dfs(int u,int f,int T)
{
    dp[u][0]=val[u];
    for(int i=0;i<edge[u].size();i++)
    {
        int v=edge[u][i].first;
        if(v==f || flag[v]) continue;
        int w=edge[u][i].second;
        dfs(v,u,T-w);
        for(int x=T;x>=0;x--)
        {
            int tmp=-1;
            for(int i=0;i<=x;i++) if(x-i-2*w>=0 && dp[v][x-i-2*w]!=-1 && dp[u][i]!=-1)
            {
                Max(tmp,dp[u][i]+dp[v][x-i-2*w]);
            }
            Max(dp[u][x],tmp);
        }
    }
}
int ans[510];
int mm[maxn][maxn];
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&T)!=EOF)
    {
        for(int i=1;i<=n;i++) edge[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            edge[a].PB(MP(b,c));
            edge[b].PB(MP(a,c));
            mm[a][b]=mm[b][a]=c;
        }
        for(int i=1;i<=n;i++) scanf("%d",&val[i]);
        memset(pre,-1,sizeof(pre));
        memset(flag,false,sizeof(flag));
        dfs1(1,0);
        flag[1]=true;
        int test=0;
        for(int i=n;i!=1;i=pre[i])
        {
            test+=mm[i][pre[i]];
            flag[i]=true;
        }
        if(test>T)
        {
            printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
            continue;
        }
        T-=test;
        memset(dp,-1,sizeof(dp));
        for(int i=1;i<=n;i++) if(flag[i]) dfs(i,0,T);
        memset(ans,-1,sizeof(ans));
        ans[0]=0;
        for(int i=n;i!=-1;i=pre[i])
        {
            for(int m=T;m>=0;m--)
            {
                for(int j=0;j<=m;j++) if(ans[m-j]!=-1 && dp[i][j]!=-1)
                {
                    Max(ans[m],ans[m-j] + dp[i][j]);
                }
            }
        }
        int ret=0;
        for(int i=0;i<=T;i++) Max(ret,ans[i]);
        printf("%d\n",ret);
    }
    return 0;
}
/*
4 3
1 4 1
4 2 0
2 3 1
10 10 10 10
5 3
1 5 1
5 2 0
2 3 0
3 4 1
10 10 10 10 10
*/

补充：软件开发 , C++ ,