關于傳說中的"樹型動態(tài)規(guī)劃"在討論題目的時候CC提及過。最近有幸找到一篇論文，相當激動，發(fā)現(xiàn)這個東東也比動態(tài)規(guī)劃本身更容易理解。

先來看一個比較有挑戰(zhàn)性的題目：）

戰(zhàn)略游戲

Problem
Bob喜歡玩電腦游戲，特別是戰(zhàn)略游戲。但是他經(jīng)常無法找到快速玩過游戲的辦法。現(xiàn)在他有個問題。
他要建立一個古城堡，城堡中的路形成一棵樹。他要在這棵樹的結(jié)點上放置最少數(shù)目的士兵，使得這些士兵能了望到所有的路。
注意，某個士兵在一個結(jié)點上時，與該結(jié)點相連的所有邊將都可以被了望到。
請你編一程序，給定一樹，幫Bob計算出他需要放置最少的士兵.


Input
第一行為一整數(shù)Ｍ，表示有Ｍ組測試數(shù)據(jù)
每組測試數(shù)據(jù)表示一棵樹，描述如下：
第一行 N，表示樹中結(jié)點的數(shù)目。
第二行至第N+1行，每行描述每個結(jié)點信息，依次為：該結(jié)點標號i，k(后面有k條邊與結(jié)點I相連)。
接下來k個數(shù)，分別是每條邊的另一個結(jié)點標號r1，r2，...，rk。
對于一個n(0<n<=1500)個結(jié)點的樹，結(jié)點標號在0到n-1之間，在輸入數(shù)據(jù)中每條邊只出現(xiàn)一次。


Output
輸出文件僅包含一個數(shù)，為所求的最少的士兵數(shù)目。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

這個題目是04年高二準備NOIP的時候看到過，當時打死沒有想出有效的解決方法。然后就拿著題目去問我們廖老師，廖老師一拿到題目題目還沒看完，立馬給出了解決方案：不會考這么難的題。于是這個題目也就遺留了下來，沒想到事隔這么多年以后又重新見識了這個題目，倍感親切，呵呵~。

這個題目看上去想圖論，貪心是明顯錯誤的。用動態(tài)規(guī)劃的思想可以很有效地解決。就看你能不能看出來是動態(tài)規(guī)劃。就像楊瀟說的：動態(tài)規(guī)劃這類題，別人一說就明白，自己就很難想到。
在給出這個題目的狀態(tài)轉(zhuǎn)移方程之前，我們先從更簡單的樹型動態(tài)規(guī)劃入手，看看其他一些題目。

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>


二叉蘋果樹

題目
有一棵蘋果樹，如果樹枝有分叉，一定是分2叉（就是說沒有只有1個兒子的結(jié)點）
這棵樹共有N個結(jié)點（葉子點或者樹枝分叉點），編號為1-N,樹根編號一定是1。
我們用一根樹枝兩端連接的結(jié)點的編號來描述一根樹枝的位置。下面是一顆有4個樹枝的樹
   2   5
    \ /
     3   4
      \ /
       1
現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。
給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。


輸入格式
第1行2個數(shù)，N和Q(1<=Q<= N,1<N<=100)。
N表示樹的結(jié)點數(shù)，Q表示要保留的樹枝數(shù)量。接下來N-1行描述樹枝的信息。
每行3個整數(shù)，前兩個是它連接的結(jié)點的編號。第3個數(shù)是這根樹枝上蘋果的數(shù)量。
每根樹枝上的蘋果不超過30000個。


輸出格式
一個數(shù)，最多能留住的蘋果的數(shù)量。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

分析：因為樹是二叉的，所以狀態(tài)轉(zhuǎn)移方程很容易寫出，
我們用a[i][j]描述樹，f[i][m]表示第i個節(jié)點下，共保留m個樹枝的最大蘋果數(shù)目。
方程：f[i][m]=mas{ f[L][n]+f[m-n-2]+a[i][L]+a[i][ R]} 0<=n<=m-2 其中L,R為i的左右子樹

選課

[問題描述]
在大學里每個學生，為了達到一定的學分，必須從很多課程里選擇一些課程來學習，在課程里有些課程必須在某些課程之前學習，如高等數(shù)學總是在其它課程之前學習。現(xiàn)在有N門功課，每門課有個學分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即只有學完了課程a，才能學習課程b）。一個學生要從這些課程里選擇M門課程學習，問他能獲得的最大學分是多少？


輸入：
第一行有兩個整數(shù)N,M用空格隔開。(1<=N<=200,1<=M<=150)
接下來的N行,第I+1行包含兩個整數(shù)ki和si, ki表示第I門課的直接先修課，si表示第I門課的學分。若ki=0表示沒有直接先修課（1<=ki<=N, 1<=si<=20）。


輸出：
只有一行，選M門課程的最大得分。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

分析：這個題目是一個普通的樹，關鍵步驟就是把這個普通的樹轉(zhuǎn)換為一顆二叉樹，并且處理的時候特殊處理一下右子樹。我自認為普通樹轉(zhuǎn)化為二叉樹以后很難處理各個節(jié)點的輩份關系，但是對于這個題目來說，如果節(jié)點1,2,3都是節(jié)點0的孩子,那么轉(zhuǎn)換后便成了這樣:
    0                         0            
  / |  \       ---->         /
1  2  3                  1－2－3
輩份雖然變了，但是還是有辦法處理的。
方程：f[i][k]表示第i個節(jié)點下總共選擇k門課的最大得分。s[i]表示課程i的得分。則
f[i][k]=max{ s[i]+f[i.L][j]+f[i.R][k-j-1] , f[i.R][k] } (0<=j<k)
其中后邊那個f[i.R][k]就是處理轉(zhuǎn)換為二叉樹時的關系的。

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

看到這里，樹型動態(tài)規(guī)劃應該可以有個初步了解了，那么我們回到最初的那個題目“戰(zhàn)略游戲”。
分析：首先選定一個節(jié)點作為根，然后從葉子向上DP，對于每個節(jié)點來說，分別記錄它放士兵和不放士兵，其子樹的最少士兵數(shù)。如果該節(jié)點放士兵，則不會制約它的子樹和父親，但是如果不放士兵，則會其子樹和父親都會影響。所以在設計動態(tài)轉(zhuǎn)移方程的時候要有開闊的思路。
方程：f[v][0],f[v][1]分別表示節(jié)點v沒有士兵和有士兵時，該子樹中最少的士兵數(shù)。方程分兩個
f[v][0]={ ∑f[v.Son][1] }   //若該節(jié)點不放士兵,則它的孩子都放士兵
f[v][1]={ ∑min{ f[v.Son][0], f[v.Son][1] }+1 }    //若該節(jié)點放士兵,則它的孩子可以放士兵也可以不放

這樣問題便完美解決了,時間復雜度O(n2)

下面再來一個題目作為思路擴展,和剛剛的題目類似:


沒有上司的晚會

背景
有個公司要舉行一場晚會。
為了能玩得開心，公司領導決定：如果邀請了某個人，那么一定不會邀請他的上司
（上司的上司，上司的上司的上司……都可以邀請）。


題目
每個參加晚會的人都能為晚會增添一些氣氛，求一個邀請方案，使氣氛值的和最大。

輸入格式
第1行一個整數(shù)N（1<=N<=6000）表示公司的人數(shù)。
接下來N行每行一個整數(shù)。第i行的數(shù)表示第i個人的氣氛值x(-128<=x<=127)。
接下來每行兩個整數(shù)L，K。表示第K個人是第L個人的上司。
輸入以0 0結(jié)束。


輸出格式
一個數(shù)，最大的氣氛值和。