Apple Tree POJ - 2486 （树形dp）

佚名 6年前 (2019-04-26) 随笔 1154人围观抢沙发百度已收录

题目链接：

D - 树形dp

POJ - 2486

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题目大意：一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走V步，最多能遍历到的权值

学习网址：https://blog.csdn.net/Aria461863631/article/details/82356420

具体思路：

dp[root][j][0]为从root出发，走j步并且最终回到原来点（中间也有可能回到原来的点，但是会继续往下走）的情况下，回到root节点的权值最大值。

dp[root][j][1]为从root出发，走j步并且最终不会到原来点（中间也有可能回到原来的点，但是会继续往下走）的情况下，回到root节点的权值最大值。

dp[root][j][0]=max(dp[root][j][0],dp[root][j-i][0]+dp[son][i-2][0]);

从当前的root出发，先计算从root开始走j-i步并且回到root的时候（遍历其他子树）的最大值，再加上走当前的son节点并且回来的时候最大值，

之所以是i-2的原因是，从s出发到t，然后从t再回到s，这一共是额外的两步，所以是i-2。

dp[root][j][1]=max(dp[root][j][1],dp[root][j-i][0]+dp[son][i-1][1]);

从当前的root出发，先计算从root出发走j-i步并且回到root的时候（遍历其他的子树）的最大值，在加上到达son，并且从son出发，不再回到root节点的最大值。

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

从当前root节点出发，先计算从root到son节点走i-2步并且回到root的时候的最大值，然后再去从root节点出发，到达剩余子树并且最终不回到root节点的最大值。

AC代码：

 1 #include<iostream>  2 #include<stdio.h>  3 #include<cmath>  4 #include<algorithm>  5 #include<string>  6 #include<cstring>  7 #include<vector>  8 using namespace std;  9 # define ll long long 10 const int maxn = 2e5+100; 11 # define inf 0x3f3f3f3f 12 int dp[200+10][200+10][2]; 13 int vis[maxn]; 14 int sto[maxn]; 15 vector<int>Edge[maxn]; 16 int n,k; 17 void init() 18 { 19 for(int i=0; i<=n; i++) 20  { 21 vis[i]=0; 22  Edge[i].clear(); 23 // for(int j=0; j<=k; j++) 24 // { 25 // dp[i][j][0]=0; 26 // dp[i][j][1]=0; 27 // } 28  } 29 } 30 void dfs(int u,int dep) 31 { 32 for(int i=0; i<=k; i++) 33  { 34 dp[u][i][0]=dp[u][i][1]=sto[u]; 35  } 36 vis[u]=1; 37 for(int i=0; i<Edge[u].size(); i++) 38  { 39 int to=Edge[u][i]; 40 if(vis[to]) 41 continue; 42 dfs(to,dep-1); 43 for(int i1=k; i1>=1; i1--) 44  { 45 for(int i2=1; i2<=i1; i2++) 46 47  { 48 if(i2-2>=0) 49 dp[u][i1][0]=max(dp[u][i1][0], 50 dp[u][i1-i2][0]+dp[to][i2-2][0]); 51 if(i2-1>=0) 52 dp[u][i1][1]=max(dp[u][i1][1], 53 dp[u][i1-i2][0]+dp[to][i2-1][1]); 54 if(i2-2>=0) 55 dp[u][i1][1]=max(dp[u][i1][1], 56 dp[u][i1-i2][1]+dp[to][i2-2][0]); 57  } 58  } 59  } 60 } 61 int main() 62 { 63 while(~scanf("%d %d",&n,&k)){ 64 int st,ed; 65  init(); 66 for(int i=1; i<=n; i++){ 67 scanf("%d",&sto[i]); 68  } 69 for(int i=1; i<n; i++){ 70 scanf("%d %d",&st,&ed); 71  Edge[st].push_back(ed); 72  Edge[ed].push_back(st); 73  } 74 dfs(1,k); 75 printf("%d\n",max(dp[1][k][1],dp[1][k][0])); 76  } 77 return 0; 78 }