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]=max(f[u][j+2][1],f[u][j-k][1]+f[v][k][1]);$
• 如果不返回$u$点，停留在子树中
  $f[u][j+1][0]=max(f[u][j+1][0],f[u][j-k][1]+f[v][k][0]);$
• 如果不返回$u$点，不停留在子树中
  $f[u][j+2][0]=max(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;
}

这篇关于POJ - 2486 :Apple Tree 树上有依赖背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---