題目描述

某大學(xué)有N個職員，編號為1~N。他們之間有從屬關(guān)系，也就是說他們的關(guān)系就像一棵以校長為根的樹，父結(jié)點就是子結(jié)點的直接上司。現(xiàn)在有個周年慶宴會，宴會每邀請來一個職員都會增加一定的快樂指數(shù)Ri，但是呢，如果某個職員的上司來參加舞會了，那么這個職員就無論如何也不肯來參加舞會了。所以，請你編程計算，邀請哪些職員可以使快樂指數(shù)最大，求最大的快樂指數(shù)。

輸入輸出格式

輸入格式：

第一行一個整數(shù)N。(1<=N<=6000)

接下來N行，第i+1行表示i號職員的快樂指數(shù)Ri。(-128<=Ri<=127)

接下來N-1行，每行輸入一對整數(shù)L,K。表示K是L的直接上司。

最后一行輸入0 0

輸出格式：

輸出最大的快樂指數(shù)。

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

5

思路：經(jīng)典的樹形dp

使用?vector<int> son[N]，用 son[i] 來保存節(jié)點 i 的所有兒子

用?f[x][0] 表示以 x 為根的子樹，且 x 不參加舞會的最大快樂值；用?f[x][1] 表示以 x 為根的子樹，且 x 參加了舞會的最大快樂值

則有狀態(tài)轉(zhuǎn)移方程：f[x][0]=∑{max(f[y][0],f[y][1])}，f[x][1]=∑{f[y][0]}+happy[x]，其中 y 是 x 的兒子

找到唯一的樹根 root，則有 res=max(f[root][0],f[root][1])

源代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<ctime> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 10001 #define MOD 10007 #define E 1e-6 #define LL long long using namespace std; vector<int> son[N]; int happy[N]; bool vis[N]; int f[N][2]; void treeDP(int x){f[x][0]=0;//如果沒去，為0f[x][1]=happy[x];//如果去了，為相應(yīng)happy值for(int i=0;i<son[x].size();i++){//枚舉x的所有孩子int y=son[x][i];treeDP(y);//遞歸f[x][0]+=max(f[y][0],f[y][1]);//父親沒去的值為孩子去或不去的最大值f[x][1]+=f[y][0];//父親去了的值為孩子不去的值} } int main() {int n;cin>>n;for(int i=1;i<=n;i++)cin>>happy[i];for(int i=1;i<=n-1;i++){int x,y;cin>>x>>y;son[y].push_back(x);//存儲職員關(guān)系vis[x]=true;//標(biāo)記}int root;for(int i=1;i<=n;i++){ //尋找根節(jié)點if(!vis[i]){root=i;break;}}treeDP(root);//對根節(jié)點進行dpint res=max(f[root][0],f[root][1]);//比較根節(jié)點去或不去cout<<res<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的没有上司的舞会（洛谷-P1352）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。