題目網址: http://poj.org/problem?id=2342
題意: 有間公司有N個員工(1...N)，現在要開始一個party，由於每個人都不想與自己的直接上司共同在場，且每個人都有一個歡樂值，如果直接上司不在場，則此人擁有其歡樂值，現在給定N-1個員工關係L K，分別代表員工K為員工L的直接上司，問你要邀請哪些人才能擁有全場最大歡樂值，最後輸出最大歡樂值。
解法: 整個公司的所有員工(包含老闆-root)，會形成一個樹狀結構，以dp[i][j]代表以員工i為樹根的子樹j情況(j == 0, 員工i不在場; j == 1, 員工i在場)時的最大歡樂值，而狀態轉移方程:
dp[i][j] = { tree[i].val+{ dp[k][0], for k是i的直接下屬 }, if j == 1
{ { max( dp[k][0], dp[k][1] ), for k是i的直接下屬 }, if j == 0
*tree[i].val 表示員工i的歡樂值
當員工i在場時，最大歡樂值為所有i的直接下屬不在場歡樂值的和再加上員工i的歡樂值；若員工i不在場，最大歡樂值為所有i的直接下屬在場或不在場(取最大)的和。
再以DFS考慮"老闆"在場或不在場的情況，答案為 max( dp[老闆][0], dp[老闆][1] )。
TAG: TreeDP, DFS, DP
注意: None
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽