POJ2486Apple Tree

题意：有棵n个节点的苹果树，每个节点有一定数量的苹果，从一个节点到另一个节点需要花费1步，给定最多步数K，求最多能吃到多少苹果？

1.    这道题开始稍微一看就大概知道是树形+背包的DP，但是一直在一个地方卡住，因为子树的遍历分为要不要回到原来的父节点，后来受不了看了题解才知道，他能是直接加多一维，表示是否要回来父节点

2.    DP方程：

直接遍历完直接回来父节点的情况：

g[pos].f[i][1]=max(g[pos].f[i][1],g[pos].f[i-j][1]+g[p].f[j-2][1]);

不回到父节点的情况

g[pos].f[i][0]=max(g[pos].f[i][0],g[pos].f[i-j][0]+g[p].f[j-2][1]);

回到父节点不过继续去遍历之前的子节点(这是最难想到的一种情况)

g[pos].f[i][0]=max(g[pos].f[i][0],g[pos].f[i-j][0]+g[p].f[j-2][1]);

1表示还要回来，0不需要回来

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 105
#define M 205
using namespace std;
struct Node
{
int w;
int f[M][2];//1 means it can come back
//0 means it can not come back
int son[N];
int coun;
}g[N];
int n,m;
void DFS(int pos,int father)
{
int p;
for(int i=0;i<g[pos].coun;++i)
{
p=g[pos].son[i];
if(p == father) continue;
DFS(p,pos);
for(int i=m;i>=1;--i)
{
for(int j=i;j>=2;--j)
{
g[pos].f[i][1]=max(g[pos].f[i][1],g[pos].f[i-j][1]+g[p].f[j-2][1]);
g[pos].f[i][0]=max(g[pos].f[i][0],g[pos].f[i-j][0]+g[p].f[j-2][1]);
}
for(int j=i;j>=1;--j)
{
g[pos].f[i][0]=max(g[pos].f[i][0],g[pos].f[i-j][1]+g[p].f[j-1][0]);
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&n,&m) != EOF)
{
memset(g,0,sizeof(g));
for(int i=1;i<=n;++i)
{
scanf("%d",&g[i].w);
for(int j=0;j<=m;++j)
{
g[i].f[j][0]=g[i].w;
g[i].f[j][1]=g[i].w;
}
}
int X,Y;
for(int i=1;i<n;++i)
{
scanf("%d%d",&X,&Y);
g[X].son[g[X].coun++]=Y;
g[Y].son[g[Y].coun++]=X;
}
DFS(1,-1);
int ans=0;
for(int i=0;i<=m;++i)
{
ans=max(ans,g[1].f[i][0]);
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是幽默金毛为你收集整理的POJ2486Apple Tree的全部内容，希望文章能够帮你解决POJ2486Apple Tree所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。