首页 > 代码库 > HDU 1520 Anniversary party
HDU 1520 Anniversary party
http://acm.hdu.edu.cn/showproblem.php?pid=1520
题意：
将有一个党庆祝乌拉尔国立大学80周年。大学有一个员工的层次结构。这意味着监督关系形成了一个树根源于校长VE Tretyakov。为了使党对每个人都有趣，主任不想让一个雇员和他或她的直接主管在场。人事局已评估每个员工的欢乐性，所以每个人都有一定数量（评级）附加到他或她。你的任务是制作一个客人的列表，其中有最大可能的客人的欢乐度评分的总和。
思路：
这道题目就是UVa 1220的减弱版，比较基本的树形DP。
d[u][1]代表以u为根的子树中，选u能得到的最大欢乐度。d[u][0]代表不选u能得到的最大欢乐度。
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 8 int n; 9 int a[6005];10 int d[6005][2];11 12 vector<int> sons[6005];13 14 void dfs(int u)15 {16 if (sons[u].size() == 0)17 {18 d[u][1] = a[u];19 d[u][0] = 0;20 return;21 }22 23 if (d[u][1]) return;24 25 int k = sons[u].size();26 for (int i = 0; i < k; i++)27 {28 int son = sons[u][i];29 dfs(son);30 d[u][1]+= d[son][0];31 32 d[u][0]+= max(d[son][1], d[son][0]);33 }34 d[u][1] += a[u];35 }36 37 int main()38 {39 //freopen("D:\\txt.txt", "r", stdin);40 int x, y;41 while (cin >> n)42 {43 memset(d, 0, sizeof(d));44 for (int i = 1; i <= n; i++)45 {46 cin >> a[i];47 sons[i].clear();48 }49 while (cin >> x>> y)50 {51 if (x == 0 && y == 0) break;52 sons[y].push_back(x);53 }54 55 int Max = 0;56 for (int i = 1; i <= n; i++)57 {58 dfs(i);59 Max = max(Max, max(d[i][1], d[i][0]));60 }61 cout << Max << endl;62 }63 return 0;64 }
HDU 1520 Anniversary party
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。