hdu 1520 Anniversary party (树形dp模板题)

题目链接题意：一个舞会，每个人有一个val，给出n个人之间的领导和被领导关系，一个人不愿意与他的领导同时参加，问一种安排方案，使得参加的人的val和最大，问这个最大的和是多少。

思路：树形dp模板题。

dp1[v]表示包含v节点的子树的最大值。

dp2[v]表示，不包含v节点的子树的最大值。

下面讲得很清楚。。

Now, similar to array problem, we have to make a decision about including node V in our subset or not. If we include node V, we can’t include any of its children(say _v_1, _v_2, …, v__n), but we can include any grand child of V. If we don’t include V, we can include any child of V.
So, we can write a recursion by defining maximum of two cases.
.
As we see in most DP problems, multiple formulations can give us optimal answer. Here, from an implementation point of view, we can define an easier solution using DP. We define two DPs,
and
, denoting maximum coins possible by choosing nodes from subtree of node V and if we include node V in our answer or not, respectively. Our final answer is maximum of two case i.e.
.
And defining recursion is even easier in this case.
(since we cannot include any of the children) and
(since we can include children now, but we can also choose not include them in subset, hence max of both cases).

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年11月30日 星期三 20时37分22秒
 4File Name :code/hdu/1520.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=6E3+7;
32int a[N];
33int n;
34int dp1[N],dp2[N];
35vector <int>edge[N];
36int in[N];
37int root;
38void dfs(int u,int pre)
39{
40    int sum1=0,sum2=0;
41    for ( auto v: edge[u])
42    {
43	if (v==pre) continue;
44	dfs(v,u);
45	sum1+=dp2[v];
46	sum2+=max(dp1[v],dp2[v]);
47    }
48    dp1[u] = a[u] + sum1;
49    dp2[u] = sum2;
50}
51int main()
52{
53	#ifndef  ONLINE_JUDGE
54	freopen("code/in.txt","r",stdin);
55  #endif
56	while (~scanf("%d",&n))
57	{
58	    ms(in,0);
59	    ms(dp1,0);
60	    ms(dp2,0);
61	    for ( int i = 1 ;i <= n ; i++) edge[i].clear();
62	    for ( int i = 1; i <= n ; i++) scanf("%d",&a[i]);
63	    int u,v;
64	    while (~scanf("%d%d",&u,&v))
65	    {
66		if (u==0&&v==0) break;
67		edge[u].push_back(v);
68		edge[v].push_back(u);
69		in[u]++;
70	    }
71	    for ( int i = 1 ; i <= n ; i++)
72		if (in[i]==0)
73		{
74		    root = i;
75		    break;
76		}
77	    dfs(root,-1);
78	    int ans = max(dp1[root],dp2[root]);
79	    printf("%d\n",ans);
80	}
81  #ifndef ONLINE_JUDGE
82  fclose(stdin);
83  #endif
84    return 0;
85}

相关文章