hdu1520_树形dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1520

题意：

给出一棵树每个节点有权值要求父节点和子节点不能同时取求能够取得的最大值

思路：

树形dp的入门题

f[u][0]表示以u为顶点的子树，不选u点的情况下最大值
f[u][1]表示以u为顶点的子树，选u点的情况下最大值
那么，

f[u][0] = sum{ max{f[v][0], f[v][1]}, v是u的儿子节点}； //当不选u点时，它的儿子节点可以不选也可以选
f[u][1] = val[u] + sum{f[v][0], v是u的儿子节点} //当选了u点时，它的儿子节点必须是不能选

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 #include <vector>
10 #define N 6005
11 using namespace std;
12 
13 int n, val[N], dp[N][2], lab[N], vis[N];
14 vector <int> v[N];
15 void dfsdp(int p)
16 {
17     dp[p][1] = val[p];
18     dp[p][0] = 0;
19     vis[p] = 1;
20     for(int i = 0; i < v[p].size(); i++)
21     {
22         if(vis[v[p][i]] == 1)continue;
23         dfsdp(v[p][i]);
24         dp[p][0] += max(dp[v[p][i]][1], dp[v[p][i]][0]); 
25         dp[p][1] += dp[v[p][i]][0];
26     } 
27 }
28 int main()
29 {
30     int x, y;
31     while(~scanf("%d", &n))
32     {
33         memset(dp, 0, sizeof(dp));
34         for(int i = 1; i <= n; i++)
35         {
36             scanf("%d", val + i);
37             v[i].clear();
38         }
39         memset(lab, 0, sizeof(lab));
40         while(~scanf("%d %d", &x, &y) && x && y)
41         {
42             v[y].push_back(x);
43             lab[x]++;
44         }
45         for(int i = 1; i <= n; i++)
46         {
47             memset(vis, 0, sizeof(vis));
48             if(lab[i])continue;
49             dfsdp(i);
50             printf("%d
", max(dp[i][0], dp[i][1]));
51         }
52     }
53     return 0;
54 }