POJ 2342 &&HDU 1520 Anniversary party 树形DP 水题

一个公司的职员是分级制度的，所有员工刚好是一个树形结构，现在公司要举办一个聚会，邀请部分职员来参加。

要求：

1.为了聚会有趣，若邀请了一个职员，则该职员的直接上级（即父节点）和直接下级（即儿子节点）都不能被邀请

2.每一个员工都有一个兴奋值，在满足1的条件下，要使得邀请来的员工的兴奋值最高

输出最高的兴奋值。

简单的树形DP

dp[i][1]:表示以i为根的子树，邀请节点i的最大兴奋值

dp[i][0]:表示以i为根的子树，不邀请节点i的最大兴奋值

先根据入度找出整棵树的根节点，

然后一次DFS即可。

poj提交代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 using namespace std;
 5 
 6 const int maxn=6005;
 7 const int inf=0x3f3f3f3f;
 8 
 9 inline int max(int x,int y)
10 {
11     return x>y?x:y;
12 }
13 
14 int dp[maxn][2];
15 int in[maxn];
16 int rate[maxn];
17 struct Edge
18 {
19     int to,next;
20 };
21 Edge edge[maxn];
22 int head[maxn];
23 int tot;
24 
25 void init()
26 {
27     memset(head,-1,sizeof head);
28     tot=0;
29     memset(in,0,sizeof in);
30 }
31 
32 void addedge(int u,int v)
33 {
34     edge[tot].to=v;
35     edge[tot].next=head[u];
36     head[u]=tot++;
37 }
38 
39 void dfs(int u,int pre);
40 
41 int main()
42 {
43     int n;
44     while(~scanf("%d",&n))
45     {
46         init();
47         scanf("%d",&rate[1]);
48         if(!n&&!rate[1])
49             break;
50         for(int i=2;i<=n;i++)
51         {
52             scanf("%d",&rate[i]);
53         }
54         for(int i=1;i<n;i++)
55         {
56             int u,v;
57             scanf("%d%d",&v,&u);
58             addedge(u,v);
59             in[v]++;
60         }
61         int root;
62         for(int i=1;i<=n;i++)
63         {
64             if(!in[i])
65             {
66                 root=i;
67                 break;
68             }
69         }
70         dfs(root,-1);
71         printf("%d
",max(dp[root][0],dp[root][1]));
72     }
73     return 0;
74 }
75 
76 void dfs(int u,int pre)
77 {
78     dp[u][1]=rate[u];
79     dp[u][0]=0;
80     for(int i=head[u];~i;i=edge[i].next)
81     {
82         int v=edge[i].to;
83         if(v==pre)
84             continue;
85         dfs(v,u);
86         dp[u][1]+=dp[v][0];
87         dp[u][0]+=max(dp[v][1],dp[v][0]);
88     }
89 }

View Code

HDU的1520和POJ的2342是一样的，但是输入有点不同

hdu提交代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 using namespace std;
 5 
 6 const int maxn=6005;
 7 const int inf=0x3f3f3f3f;
 8 
 9 inline int max(int x,int y)
10 {
11     return x>y?x:y;
12 }
13 
14 int dp[maxn][2];
15 int in[maxn];
16 int rate[maxn];
17 struct Edge
18 {
19     int to,next;
20 };
21 Edge edge[maxn];
22 int head[maxn];
23 int tot;
24 
25 void init()
26 {
27     memset(head,-1,sizeof head);
28     tot=0;
29     memset(in,0,sizeof in);
30 }
31 
32 void addedge(int u,int v)
33 {
34     edge[tot].to=v;
35     edge[tot].next=head[u];
36     head[u]=tot++;
37 }
38 
39 void dfs(int u,int pre);
40 
41 int main()
42 {
43     int n;
44     while(~scanf("%d",&n))
45     {
46         init();
47         for(int i=1;i<=n;i++)
48         {
49             scanf("%d",&rate[i]);
50         }
51         while(true)
52         {
53             int u,v;
54             scanf("%d%d",&v,&u);
55             if(!u&&!v)
56                 break;
57             addedge(u,v);
58             in[v]++;
59         }
60         int root;
61         for(int i=1;i<=n;i++)
62         {
63             if(!in[i])
64             {
65                 root=i;
66                 break;
67             }
68         }
69         dfs(root,-1);
70         printf("%d
",max(dp[root][0],dp[root][1]));
71     }
72     return 0;
73 }
74 
75 void dfs(int u,int pre)
76 {
77     dp[u][1]=rate[u];
78     dp[u][0]=0;
79     for(int i=head[u];~i;i=edge[i].next)
80     {
81         int v=edge[i].to;
82         if(v==pre)
83             continue;
84         dfs(v,u);
85         dp[u][1]+=dp[v][0];
86         dp[u][0]+=max(dp[v][1],dp[v][0]);
87     }
88 }

View Code