POJ - 2486 :Apple Tree 树上有依赖背包

本文主要是介绍POJ - 2486 :Apple Tree 树上有依赖背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题目描述

一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走k步，最多能遍历到的权值。

分析

首先我们可以去dfs每一个为为根节点的时候，子树走 $k$ 步的时候的最大权值，但这里涉及到一位问题，因为每一条边可以重复走，所以会不会有回头的情况
我们用 $f [i] [j] [0 / 1]$ 表示在 $i$ 点的时候，走 $k$ 步，是否返回 $i$ 节点的情况下所能获得的最大权值，然去去状态转移就可以了

如果返回 $u$ 点，那么
$f [u] [j + 2] [1] = m a x (f [u] [j + 2] [1], f [u] [j - k] [1] + f [v] [k] [1]);$
如果不返回 $u$ 点，停留在子树中
$f [u] [j + 1] [0] = m a x (f [u] [j + 1] [0], f [u] [j - k] [1] + f [v] [k] [0]);$
如果不返回 $u$ 点，不停留在子树中
$f [u] [j + 2] [0] = m a x (f [u] [j + 2] [0], f [u] [j - k] [0] + f [v] [k] [1]);$

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 500,M = N;
int h[N],ne[M],e[M],idx;
int a[N];
int f[N][N][2];
int n,li;void add(int x,int y){ne[idx] = h[x],e[idx] = y,h[x] = idx++;
}void dfs(int u,int fa){for(int i = 0;i <= li;i++) f[u][i][0] = f[u][i][1] = a[u];for(int i = h[u];~i;i = ne[i]){int v = e[i];if(v == fa) continue;dfs(v,u);for(int j = li;j >= 0;j--)for(int k = 0;k <= j;k++){f[u][j + 2][1] = max(f[u][j + 2][1],f[u][j - k][1] + f[v][k][1]);f[u][j + 1][0] = max(f[u][j + 1][0],f[u][j - k][1] + f[v][k][0]);f[u][j + 2][0] = max(f[u][j + 2][0],f[u][j - k][0] + f[v][k][1]);}}
}int main(){while(~scanf("%d%d",&n,&li)){memset(h,-1,sizeof h);idx = 0;for(int i = 1;i <= n;i++) scanf("%d",&a[i]);for(int i = 1;i < n;i++){int x,y;scanf("%d%d",&x,&y);add(x,y),add(y,x);}memset(f,0,sizeof f);dfs(1,-1);printf("%d\n",max(f[1][li][1],f[1][li][0]));}return 0;
}