poj 2486(树形dp)

140 阅读 0 评论 93 点赞

我是靠谱客的博主腼腆网络，这篇文章主要介绍poj 2486(树形dp)，现在分享给大家，希望可以做个参考。

复制代码

树形dp，比较经典的一个树形dp。首先很容易就可以想到用dp[root][k]表示以root为根的子树中最多走k时所能获得的最多苹果数，接下去我们很习惯地会想到将k步在root的所有子结点中分配，也就是进行一次背包，就可以得出此时状态的最优解了，但是这里还有一个问题，那就是在进行背包的时候，对于某个孩子son走完之后是否回到根结点会对后面是否还能分配有影响，为了解决这个问题，我们只需要在状态中增加一维就可以了，用dp[root][k][0]表示在子树root中最多走k步，最后还是回到root处的最大值，dp[root][k][1]表示在子树root中最多走k步，最后不回到root处的最大值。由此就可以得出状态转移方程了：

dp[root][j][0] = MAX (dp[root][j][0] , dp[root][j-k][0] + dp[son][k-2][0]);//从s出发，要回到s，需要多走两步s-t,t-s,分配给t子树k步，其他子树j-k步，都返回

dp[root][j]][1] = MAX( dp[root][j][1] , dp[root][j-k][0] + dp[son][k-1][1]) ;//先遍历s的其他子树，回到s，遍历t子树，在当前子树t不返回，多走一步

dp[root][j][1] = MAX (dp[root][j][1] , dp[root][j-k][1] + dp[son][k-2][0]);//不回到s（去s的其他子树），在t子树返回，同样有多出两步

复制代码

//
Created by Chenhongwei on 2016-03-31 Thursday 08:36
//
Copyright (c) 2016 Chenhongwei. All rights reserved.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=500;
typedef long long ll;
typedef unsigned long long ull;
vector<int> g[maxn];
int num[maxn];
int dp[maxn][maxn][2];
int n,k,ans;
void dfs(int u,int fa)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa)
continue;
dfs(v,u);
for(int j=k;j>=1;j--)
for(int t=1;t<=j;t++)
{
dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][0]+dp[v][t-2][0]);
dp[u][j][1]=max(dp[u][j][1],dp[u][j-t][0]+dp[v][t-1][1]);
dp[u][j][1]=max(dp[u][j][1],dp[u][j-t][1]+dp[v][t-2][0]);
}
}
}
int main()
{
//ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=0;i<=n;i++)
g[i].clear();
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
for(int j=0;j<=k;j++)
dp[i][j][0]=dp[i][j][1]=num[i];
}
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
g[v].push_back(u);
g[u].push_back(v);
}
dfs(1,-1);
printf("%dn",max(dp[1][k][0],dp[1][k][1]));
}
return 0;
}

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//
Created by Chenhongwei on 2016-03-31 Thursday 08:36
//
Copyright (c) 2016 Chenhongwei. All rights reserved.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=500;
typedef long long ll;
typedef unsigned long long ull;
vector<int> g[maxn];
int num[maxn];
int dp[maxn][maxn][2];
int n,k,ans;
void dfs(int u,int fa)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa)
continue;
dfs(v,u);
for(int j=k;j>=1;j--)
for(int t=1;t<=j;t++)
{
dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][0]+dp[v][t-2][0]);
dp[u][j][1]=max(dp[u][j][1],dp[u][j-t][0]+dp[v][t-1][1]);
dp[u][j][1]=max(dp[u][j][1],dp[u][j-t][1]+dp[v][t-2][0]);
}
}
}
int main()
{
//ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=0;i<=n;i++)
g[i].clear();
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
for(int j=0;j<=k;j++)
dp[i][j][0]=dp[i][j][1]=num[i];
}
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
g[v].push_back(u);
g[u].push_back(v);
}
dfs(1,-1);
printf("%dn",max(dp[1][k][0],dp[1][k][1]));
}
return 0;
}