POJ 2486 树形DP

有一颗苹果树，每个节点上面有很多苹果，从一个节点到另外一个可以到达的节点花费1步，求k步最多能吃到多少苹果，起始点为1，可以不回到起始点。

这是典型的回溯型树状dp。

dp[i][j][0]代表以i为根节点的子树最多j步后回到i能吃到的最多的苹果，

dp[i][j][1]代表以i为根节点的子树最多j步后不回到i节点最多能吃到的子树。那么状态转移就分三步了。

（1）dp[i][j+2][0] = max(dp[i][j+2][0], dp[i][j-k][0]+dp[son][k][0]);

（2）dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j-k][0]+dp[son][k][1]);  人留在i的子节点son的子树中

（3）dp[i][j+2][1] = max(dp[i][j+2][1], dp[i][j-k][1]+dp[son][k][0]);  人留在不是son的i的子节点的子树中

#include "stdio.h"
#include "string.h"
#include "vector"
using namespace std;
vector< vector<int> >data(110);
int dp[110][210][3],vis[110],v[110];
int n,m;
int Max(int a,int b)
{
if (a<b) return b;else return a;
}
void dfs(int cur)
{
int i,next,j,k;
vis[cur]=1;
for (i=0;i<=m;i++)
dp[cur][i][0]=dp[cur][i][1]=v[cur];
for (i=0;i<data[cur].size();i++)
{
next=data[cur][i];
if (vis[next]==0)
{
dfs(next);
for (j=m;j>=0;j--)
for (k=0;k<=j;k++)
{
dp[cur][j+2][0]=Max(dp[cur][j+2][0],dp[cur][j-k][0]+dp[next][k][0]);
dp[cur][j+1][1]=Max(dp[cur][j+1][1],dp[cur][j-k][0]+dp[next][k][1]);
dp[cur][j+2][1]=Max(dp[cur][j+2][1],dp[cur][j-k][1]+dp[next][k][0]);
}
}
}
}
int main()
{
int i,x,y;
while (scanf("%d%d",&n,&m)!=EOF)
{
for (i=1;i<=n;i++)
{
data[i].clear();
scanf("%d",&v[i]);
}
for (i=2;i<=n;i++)
{
scanf("%d%d",&x,&y);
data[x].push_back(y);
data[y].push_back(x);
}
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
dfs(1);
printf("%dn",dp[1][m][1]);
}
return 0;
}

最后

以上就是儒雅百合为你收集整理的POJ 2486 树形DP的全部内容，希望文章能够帮你解决POJ 2486 树形DP所遇到的程序开发问题。

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