本文主要是介绍POJ 2486 Apple Tree 树形DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有一颗苹果树，每个节点上面有很多苹果，从一个节点到另外一个可以到达的节点花费1步，求k步最多能吃到多少苹果。 dp[root][j][0]为以root为根的子树走j步路在回到root最多获得多少苹果，dp[root][j][0]为以root为根的子树走j步路不回到root最多获得多少苹果。 dp[root][j][0] = max(dp[root][j][0], dp[root][j-l][0] + dp[son][l-2][0]); dp[root][j][1] = max(dp[root][j][1], dp[root][j-l][0] + dp[son][l-1][1]); dp[root][j][1] = max(dp[root][j][1], dp[root][j-l][1] + dp[son][l-2][0]);#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Node
{
int now,next,val;
}tree[20005];
int dp[105][205][2];
int a[105];
int head[105];
int n,s,k,len;
void add(int x,int y)//建树
{
tree[len].now = y;
tree[len].next = head[x];
head[x] = len++;
}
void dfs(int root,int p)
{
for(int i = 0; i <= k; i++)
dp[root][i][0] = dp[root][i][1] = a[root];
int i,j,l,son;
for(i = head[root]; i!=-1; i = tree[i].next)
{
son = tree[i].now;
if(son == p)
continue;
dfs(son,root);
for(j = k; j>=0; j--)
{
for(l = 1; l <= j; l++)
{
if(l > 1)
dp[root][j][0] = max(dp[root][j][0], dp[root][j-l][0] + dp[son][l-2][0]);
if(l)
dp[root][j][1] = max(dp[root][j][1], dp[root][j-l][0] + dp[son][l-1][1]);
if(l > 1)
dp[root][j][1] = max(dp[root][j][1], dp[root][j-l][1] + dp[son][l-2][0]);
}
}
}
}
int main()
{
int i, x, y, w;
while(~scanf("%d %d",&n, &k))
{
len = 0;
memset(head, -1, sizeof(head));
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(i = 1; i < n; i++)
{
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, -1);
printf("%d\n", dp[1][k][1]);
}
return 0;
}这篇关于POJ 2486 Apple Tree 树形DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
