POJ2486:Apple Tree(树形DP) ★

74 阅读 0 评论 49 点赞

我是靠谱客的博主仁爱花生，最近开发中收集的这篇文章主要介绍POJ2486:Apple Tree(树形DP) ★，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走V步，最多能遍历到的权值
思路：
树形dp，比较经典的一个树形dp。首先很容易就可以想到用dp[root][k]表示以root为根的子树中最多走k时所能获得的最多苹果数，接下去我们很习惯地会想到将k步在root的所有子结点中分配，也就是进行一次背包，就可以得出此时状态的最优解了，但是这里还有一个问题，那就是在进行背包的时候，对于某个孩子son走完之后是否回到根结点会对后面是否还能分配有影响，为了解决这个问题，我们只需要在状态中增加一维就可以了，用dp[root][k][0]表示在子树root中最多走k步，最后还是回到root处的最大值，dp[root][k][i]表示在子树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子树返回，同样有多出两步

注意递推时要从后往前，不然一个子节点会被算两次

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define L(i) i<<1
#define R(i) i<<1|1
#define INF
0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-9
#define maxn 60010
#define MOD 1000000007
struct node
{
int to,next;
} edge[505];
int dp[205][405][2],head[205],val[205];
int tot,n,k;
void add(int u,int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u,int pre)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(v == pre)
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()
{
int t,C = 1;
//scanf("%d",&t);
while(scanf("%d%d",&n,&k) != EOF)
{
memset(dp,0,sizeof(dp));
memset(head,-1,sizeof(head));
tot = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d",&val[i]);
for(int j = 0; j <= k; j++)
dp[i][j][0] = dp[i][j][1] = val[i];
}
for(int i = 1; i < n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,0);
printf("%dn",max(dp[1][k][0],dp[1][k][1]));
}
return 0;
}