POJ 2486 Apple Tree

浏览数：24 / 时间：2015年06月11日

　　很好也很烦的一个树形DP，昨天搞了一晚上是在想不出，后来没办法去看题解了，完事发现非常令人感动的是，我一开始设的状态都错了，然后就一直错了下去，还好及时的回头是岸了。

　　不说废话了，正题：

　　题目大意：给一棵树，n个节点，每个节点有一个权值，要求从节点1出发最多走k步，求所经过的点的权值和的最大值，每个点经过一次后就变为0；

　　最近做了一些树DP 也小小的总结了点规律，树形dp一般是设dp[rt][j]即以rt为根的子树j状态。这个题可以设

　　dp[rt][j][0]表示以rt为根的子树走j步最后不回到rt的解

　　dp[rt][j][1]表示以rt为根的子树走j步最后回到rt的解

　　方程看代码

　　然后对于每个儿子节点进行一次背包，背包容量为步数，看了半天题解一直感觉方程根本就不对，后来看到了是背包，(个人对于背包的一个描述就是放与不放的问题)，想了一下恍然大悟

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <cmath>
 8 #include <map>
 9 #define INF 0x3f3f3f3f
10 typedef __int64 LL;
11 const int maxn = 110;
12 const int maxv = 210;
13 using namespace std;
14 int dp[maxn][maxv][2],a[maxn];
15 vector<int>son[maxn];
16 vector<int>f[maxn];
17 bool vis[maxn];
18 int n,m;
19 void build_tree(int rt)
20 {
21     //个人比较中意的一种建树的方法
22     //首先用辅助vector f记录总共有多少条边，然后再从根节点开始dfs
23     //找出与rt相连的边让其成为rt的子节点，然后vis标记这条边已经属于子节点
24     //不能再成为别的节点的子节点
25     //最后son[rt]中的元素都是rt的子节点
26     //这样做主要还是不太会用邻接表  渣渣为自己找借口。。
27     int len = f[rt].size(),x;
28     for(int i = 0;i<len;++i)if(!vis[x = f[rt][i]]){
29         son[rt].push_back(x);
30         vis[x] = 1;
31         build_tree(x);
32     }
33 }
34 void init()
35 {
36     memset(vis,0,sizeof(vis));
37     memset(son,0,sizeof(son));
38     memset(f,0,sizeof(f));
39     for(int i = 1;i<=n;++i)scanf("%d",a+i);
40     for(int i = 1;i<n;++i)
41     {
42         int s,t;
43         scanf("%d%d",&s,&t);
44         f[s].push_back(t);
45         f[t].push_back(s);
46     }
47     for(int i = 1;i<=n;++i)
48         for(int j = 0;j<=m;++j)
49             dp[i][j][0] = dp[i][j][1] = a[i];
50     vis[1] = 1;
51     build_tree(1);
52 }
53 void dfs(int rt)
54 {
55     int len = son[rt].size();
56     for(int i = 0;i<len;++i){
57         int u = son[rt][i];
58         dfs(u);
59         for(int j = m;j>=0;--j){
60             for(int k = 0;k<=j;++k){
61                 //从rt走到u最后还回到rt 因为还要回到rt 所以rt->u 和u->rt这两步要排除
62                 if(k-2>=0)dp[rt][j][1] = max(dp[rt][j][1],dp[rt][j-k][1]+dp[u][k-2][1]);
63                 //从rt走到u最后不回来  也就是把k-1大小的物品放入背包中  (k-1 是因为rt->u排除)
64                 if(k-1>=0)dp[rt][j][0] = max(dp[rt][j][0],dp[rt][j-k][1]+dp[u][k-1][0]);
65                 //从rt走到u还回来 最后停在别的儿子节点上
66                 if(k-2>=0)dp[rt][j][0] = max(dp[rt][j][0],dp[rt][j-k][0]+dp[u][k-2][1]);
67             }
68         }
69     }
70 }
71 int main()
72 {
73 //    freopen("in.txt","r",stdin);
74     while(cin>>n>>m)
75     {
76         init();
77         dfs(1);
78         cout<<max(dp[1][m][0],dp[1][m][0])<<endl;
79     }
80     return 0;
81 }