POJ 2486 树形DP

134 阅读 0 评论 89 点赞

我是靠谱客的博主儒雅百合，这篇文章主要介绍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的子节点的子树中

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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;
}