[動態規劃]OI練習題 週年紀念聚會 aniv 解題報告

週年紀念聚會

Background

校長正在籌備學校的80週年紀念聚會。由於學校的職員有不同的職務級別，可以構成一棵以校長為根的人事關係樹。每個職員都有一個唯一的整數編號（範圍在1到N之間），並且對應一個參加聚會所獲得的歡樂度。為了使每個參加聚會者都感到歡樂，校長想設法使每個職員和他（她）的直接上司不會同時參加聚會。

Problem

你的任務是設計一份參加聚會者的名單，使總的歡樂度最高。

Input

輸入的第一行是一個整數N，1<= N <= 6000

以下的N行是對應的N個職員的歡樂度（歡樂度是一個從-128到127之間的整數）

接著是學校的人事關係樹，樹的每一行格式如下：

<L> <K>

表示第K個職員是第L個職員的直接上司。

輸入以0 0表示結束

輸出：參加聚會者獲得的最大總歡樂度

 

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

【分析】

樹形動態規劃。

由於邊界條件是葉子節點，所以需要遞歸每個節點來尋找葉子節點。

F[i][0] :不選第i個節點 的最大歡樂度。

F[i][1] :選第i個節點 的最大歡樂度。

狀態轉移方程：

F[i][0]+=max{ F[x][0] ,  F[x][1] } (i與x鄰接)

F[i][1]+=Happy[i]+F[x][0] (x與i鄰接)

 目標結果：
Max{F[Root][1],F[Root][0]}

Root為根節點，即題目中的公司老闆。可以統計每個點的入度，0入度的點
即為根節點。

【我的代碼】
裸代碼RawCode

C++语言: Codee#25586

01 /*
02 *Problem: 週年紀念聚會 aniv
03 *Author: Yee-fan Zhu
04 *Email: zyfworks@gmail.com
05 *Method: DFS/DP
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 #include <vector>
10 using namespace std; 
11 const int MAXN=6001;
12 int F[MAXN][2];
13 int Happy[MAXN];
14 int N;
15 int visited[MAXN];
16 vector<int> Map[MAXN];
17 int  root=1;
18 bool flag[MAXN];
19
20 void init()
21 {
22     scanf("%d\n",&N);
23     for(int i=1;i<=N;i++)
24     {
25         scanf("%d\n",&F[i][1]);
26         visited[i]=0;
27     }
28     int x,y;
29     scanf("%d %d\n",&x,&y);
30     while(x!=0)
31     {
32         Map[y].push_back(x);
33         flag[x]=1;
34         scanf("%d %d\n",&x,&y);
35     }
36     for(int i=1;i<=N;i++)
37     {
38         if(!flag[i])
39         {
40             root=i;
41             return;
42         }
43     }
44 }
45
46 int Max(int a,int b)
47 {
48     return a>b?a:b;
49 }
50
51 void dp(int x)
52 {
53     visited[x]=1;
54     for(unsigned int i=0;i<Map[x].size();i++)
55     {
56         if(visited[Map[x][i]])
57             continue;
58         dp(Map[x][i]);
59         F[x][0]+=Max(F[Map[x][i]][0],F[Map[x][i]][1]);
60         F[x][1]+=F[Map[x][i]][0];
61     }
62 }
63
64 int main()
65 {
66     freopen("aniv.in","r",stdin);
67     freopen("aniv.out","w",stdout);
68     init();
69     dp(root);
70     printf("%d\n",Max(F[root][0],F[root][1]));
71     return 0;
72 }