两道差不多的题目，放在一起了
poj 2342:
题意：在一个公司中要举办一个聚会，每一个员工有一个奉献值。为了和谐规定直接上下级不能一起出席。让你找出奉献值之和最大为多少。
思路：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 ", max(dp[root][1], dp[root][0])); 75 } 76 return 0; 77 }
poj 3342:
代码如下：
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 #include <set> 8 #include <map> 9 #include <string> 10 #include <math.h> 11 #include <stdlib.h> 12 #include <time.h> 13 #define MP(a, b) make_pair(a, b) 14 #define PB(a) push_back(a) 15 using namespace std; 16 17 const int LEN = 1010; 18 vector<int> Map[LEN]; 19 map<string, int> mp; 20 int n, top, dp[LEN][2], is[LEN][2]; 21 22 int ch(string s){ 23 if(!mp.count(s)) mp[s] = top++; 24 return mp[s]; 25 } 26 27 void dfs(int v, int fa){ 28 int tmp = 0,tmpa = 0; 29 dp[v][1] = 1;dp[v][0] = 0; 30 for(int i=0; i<Map[v].size(); i++){ 31 int x = Map[v][i]; 32 if(x != fa){ 33 dfs(x, v); 34 if(dp[x][0] == dp[x][1]) is[v][0] = 1; 35 if(dp[x][0] > dp[x][1]){ 36 dp[v][0] += dp[x][0]; 37 is[v][0] |= is[x][0]; 38 }else { 39 dp[v][0] += dp[x][1]; 40 is[v][0] |= is[x][1]; 41 } 42 dp[v][1] += dp[x][0]; 43 is[v][1] |= is[x][0]; 44 } 45 } 46 } 47 48 int main() 49 { 50 // freopen("in.txt","r",stdin); 51 //freopen("out.txt","w",stdout); 52 53 string a, b; 54 while(cin >> n && n){ 55 top = 0;mp.clear(); 56 for(int i=0; i<LEN; i++) Map[i].clear(); 57 memset(dp, 0, sizeof dp); 58 memset(is, 0, sizeof is); 59 cin >> a; 60 ch(a); 61 for(int i=0; i<n-1; i++){ 62 cin >> a >> b; 63 Map[ch(b)].PB(ch(a)); 64 } 65 dfs(0, -1); 66 int tag = 0; 67 if(dp[0][1] == dp[0][0]) tag = 1; 68 if(dp[0][1] > dp[0][0]){ 69 cout << dp[0][1] << ' '; 70 if(is[0][1]) cout << "No" << endl; 71 else cout << "Yes" << endl; 72 }else{ 73 cout << dp[0][0] << ' '; 74 if(is[0][0] | tag) cout << "No" << endl; 75 else cout << "Yes" << endl; 76 } 77 } 78 return 0; 79 }