hdu 4276 树形DP + 分组背包 - c++编程基础

题意：一棵树，让你在规定时间Ｔ内从１号节点走到ｎ号节点，并取得最多的宝藏值。
很容易可以想到一个这样子的树形DP，dp[u][t]表示u子树走t长度的距离时所能获得的最大价值，然后就是1 到 n的链上的每个点来分配容量为T的背包
其实就是一个分组背包了，链上的每个点代表每一组，每组中的物品为求得的状态dp[u][0->t]，每组至少取一个物品
还有一个注意点就是边权有可能为0，所以在树形DP转移的过程中要注意了。
以后还是尽量用tmp变量转移吧，保险- -
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 VI;
typedef vector VS;
typedef pair PII;
vector 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 {
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 {
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 {
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
*/