首页 > 代码库 > poj 3342(树形dp)

poj 3342(树形dp)

2024-07-02 10:11:24   235人阅读

题意：在一个公司中要举办一个聚会，每一个员工有一个奉献值。为了和谐规定直接上下级不能一起出席。让你找出奉献值之和最大为多少。

思路：dp[v][1]表示当前结点选，能获得的最大奉献值，dp[v][0]表示当前节点不选能获得的最大奉献值。状态转移：

dp[v][0] = max(dp[v][0], ∑max(dp[x][1], dp[x][0]))x为直接儿子

dp[v][1] = max(dp[v][1], ∑dp[x][0] + vex[v])

最后答案是max(dp[root][0], dp[root][1])

代码如下：

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-05-01 20:30
 5  * Filename     : poj_3342.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 100000+10;
34 vector<int> Map[LEN];
35 int n, rate[LEN], In[LEN], dp[LEN][2];
36 
37 void dfs(int v, int fa){
38     dp[v][0] = 0;dp[v][1] = rate[v];
39     int tmp = 0, tmpa = 0;
40     for(int i=0; i<Map[v].size(); i++){
41         int x = Map[v][i];
42         if(x == fa) continue;
43         dfs(x, v);
44         tmp += (dp[x][0]);
45         tmpa += max(dp[x][1], dp[x][0]);
46     }
47     dp[v][1] = max(dp[v][1], tmp+rate[v]);
48     dp[v][0] = max(dp[v][0], tmpa);
49 }
50 
51 int main()
52 {
53 //    freopen("in.txt", "r", stdin);
54 
55     int a, b;
56     while(scanf("%d", &n)!=EOF && n){
57         memset(In, 0, sizeof In);
58         memset(dp, 0, sizeof dp);
59         for(int i=0; i<n; i++) Map[i].clear();
60         for(int i=0; i<n; i++){
61             scanf("%d", &rate[i]);
62         }
63         for(int i=0; i<n-1; i++){
64             scanf("%d%d", &a, &b);
65             a--, b--;
66             In[a] ++;
67             Map[b].PB(a);
68         }
69         int root;
70         for(int i=0; i<n; i++){
71             if(In[i] == 0) {root = i;break;}
72         }
73         dfs(root, -1);
74         printf("%d\n", max(dp[root][1], dp[root][0]));
75     }
76     return 0;
77 }
View Code

 


联系
我们