題目網址: http://acm.timus.ru/problem.aspx?num=1018
題意: 給定一顆二叉樹，每枝樹枝上都包含Ni個蘋果(1<=i<=N)，問最後要保留Q枝樹枝，蘋果數量最大。
解法: 令dp[i][j]代表以第i個節點為樹根的子樹，砍掉j根樹枝後，所保留最多的蘋果數量，狀態轉移方程(遞迴關係式):
當要砍的枝數等於當前節點的枝數，則能保留的最多蘋果數為0；否則，考慮所有砍樹枝的情況，求最大為保留最多的蘋果數。
dp[i][j] = { 0,if j == tree[i].cnt(包含節點i的樹枝總數)
{ max{ dp[tree[i].l][k]+dp[tree[i].r][j-k] }, for 0 <= k <= j, if k <= tree[tree[i].l].cnt && (j-k) <= tree[tree[i].r].cnt
答案為 dp[1][N-1-Q]。
*tree[i].r(tree[i].l) is the right(left) child of tree[i]
TAG: DP, Tree DP
注意: None
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽