POJ 2486 Apple Tree ——(树型DP)

时间:2022-10-22 12:56:15

  题意是给出一棵树,每个点都有一个权值,从1开始,最多走k步,问能够经过的所有的点的权值和最大是多少(每个点的权值只能被累加一次)。

  考虑到一个点可以经过多次,设dp状态为dp[i][j][k],i表示当前从i出发,j表示最多走j步,k=0的话表示最后回到i点,否则不回到i点的子问题的答案。

  转移见代码。

  值得注意的是dfs中j循环的方向必须从大到小,因为如果从小到大,当前的j是从比其小的dp[u][j-t][...]更新过来的,而后者是根据走了v以后的更新过来的。换言之,如果从小到大,那么,走v贡献的权值就会被计算多次了,而题目中给的条件是,一个点的权值只能计算一次。拓展一下的话,如果一个点的权值可以被计算多次,那么应当从小到大循环j。

  不妨以下面这组数据为例可以找到区别:

  3 3
  1 100 1
  1 2
  1 3

  代码如下:

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 100 + 5;
 7 
 8 int n,k;
 9 int val[N];
10 vector<int> G[N];
11 int dp[N][N*2][2]; // 0 表示回到原地
12 void update(int & a,int b) {if(a < b) a = b;}
13 int dfs(int u,int fa)
14 {
15     for(int i=0;i<G[u].size();i++)
16     {
17         int v = G[u][i];
18         if(v == fa) continue;
19         dfs(v,u);
20         // j必须从大到小(?)
21         for(int j=k;j>=1;j--)
22         {
23             for(int t=1;t<=j;t++)
24             {
25                 // 最终都回到原地,那么左右都需要回到原地,此时需要多走两步 u->v & v->u
26                 if(t >= 2) update(dp[u][j][0], dp[u][j-t][0] + dp[v][t-2][0]);
27                 // 最终不用回到原地,有只要左边或者右边一种选择不用回到原地即可
28                 if(t >= 2) update(dp[u][j][1], dp[u][j-t][1] + dp[v][t-2][0]);
29                 update(dp[u][j][1], dp[u][j-t][0] + dp[v][t-1][1]);
30             }
31         }
32     }
33 }
34 
35 int main()
36 {
37     while(scanf("%d%d",&n,&k) == 2)
38     {
39         memset(dp,0,sizeof dp);
40         for(int i=1;i<=n;i++)
41         {
42             G[i].clear();
43             scanf("%d",val+i);
44             for(int j=0;j<=k;j++) dp[i][j][0] = dp[i][j][1] = val[i];
45         }
46         for(int i=1;i<n;i++)
47         {
48             int u,v;
49             scanf("%d%d",&u,&v);
50             G[u].push_back(v);
51             G[v].push_back(u);
52         }
53         dfs(1, -1);
54         printf("%d\n",max(dp[1][k][0], dp[1][k][1]));
55     }
56     return 0;
57 }