（HDU 1520）Anniversary party <树型DP> 公司开派对，上下级不能同时到

Anniversary party Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10356 Accepted Submission(s): 4366

PRoblem Description There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests’ conviviality ratings.

Input Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form: L K It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line 0 0

Output Output should contain the maximal sum of guests’ ratings.

Sample Input 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0

Sample Output 5

Source Ural State University Internal Contest October’2000 Students session

AC代码：

/* 2017/2/28 题意: 公司要开派对，有n个员工，为了良好的气氛，有一个规定：员工和它的直属上司不能同时参加，并且每个人有一个权值，问如何安排可以使权值之和最大？ <只能说题目输入太坑了，明明有n还要用0 0来表示边的结束> 分析： 每个员工有两种状态，参加或者不参加（如数据小我们可以暴力） 在这里无法暴力，所以我们可以想到dp（高级暴力） dp[i][0],dp[i][1]分别表示以员工i为根的子树，员工i参加和不参加的最大和值 所以我们可以找到关系： dp[i][1] += dp[j][0] (j是i的子节点) //第u个人参加，则它的下属都不能参加 dp[i][0] += max(dp[j][1],dp[j][0]) (j是i的子节点) //第u个人不参加，这下属可以参加或不参加（因为有负数值） */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> using namespace std; const int maxn = 6010; bool notroot[maxn]; int dp[maxn][2]; int root,n; int head[maxn]; int e; struct Edge { int v,next; }edges[maxn]; void addedge(int u,int v) { edges[e].v = v; edges[e].next = head[u]; head[u] = e++; } void tree_dp(int u) { for(int i=head[u];i!=-1;i=edges[i].next) { int v = edges[i].v; tree_dp(v); dp[u][1] += dp[v][0];//第u个人参加，则它的下属都不能参加 dp[u][0] += max(dp[v][1],dp[v][0]);//第u个人不参加，这下属可以参加或不参加（因为有负数值） } } int main() { int u,v; while(scanf("%d",&n)!=EOF) { memset(head,-1,sizeof(head)); memset(notroot,0,sizeof(notroot)); memset(dp,0,sizeof(dp)); e = 0; for(int i=1;i<=n;i++) scanf("%d",&dp[i][1]); while(1)//输入真坑人，卡了半天 { scanf("%d%d",&v,&u); if(!u && !v) break; addedge(u,v); notroot[v] = 1; } //找根 for(int i=1;i<=n;i++) { if(!notroot[i]) { root = i; break; } } tree_dp(root); printf("%d\n",max(dp[root][0],dp[root][1])); } return 0; }