【正文】 左子樹；因此，最后輸出的前序遍歷結(jié)果會有部分不同，但同樣是正確的。如果最大加分二叉樹的所有節(jié)點(diǎn)的度數(shù)都是0或2，則最后輸出的前序遍歷結(jié)果是唯一的。} end。 for d:=2 to n1 do begin{依次計(jì)算間距為d的兩個節(jié)點(diǎn)構(gòu)成的二叉樹的最大加分} for i:=1 to nd do begin s:=value[i,i]+value[i+1,i+d]。{計(jì)算以i為根節(jié)點(diǎn)，以i+1至i+d間所有節(jié)點(diǎn)為右子樹的二叉樹的最大加分} root[i,i+d]:=i。 {記錄根節(jié)點(diǎn)i} for j:=1 to d do begin temp:=value[i+j,i+j]+value[i,i+j1]*value[i+j+1,i+d]。{計(jì)算以i+j為根節(jié)點(diǎn)，以i至i+j1間所有節(jié)點(diǎn)為左子樹，以i+j+1至i+d間所有節(jié)點(diǎn)為右子樹的二叉樹的最大加分} if temps then begin{如果此值為最大} s:=temp。root[i,i+d]:=i+j。{記下新的最大值和新的根節(jié)點(diǎn)} end。 end。 temp:=value[i,i+d1]+value[i+d,i+d]。{計(jì)算以i+d為根節(jié)點(diǎn)，以i至i+d1間所有節(jié)點(diǎn)為左子樹的二叉樹的最大加分} if temps then begin s:=temp。root[i,i+d]:=i+d+1。 end。 value[i,i+d]:=s。 end。 end。 writeln(f2,value[1,n]:0:0)。{輸出最大加分} preorder(1,n)。{輸出最大加分二叉樹的前序遍歷序列} close(f2)。 end.技能樹（浙江省2004組隊(duì)賽第二試）Problem玩過Diablo的人對技能樹一定是很熟悉的。一顆技能樹的每個結(jié)點(diǎn)都是一項(xiàng)技能，要學(xué)會這項(xiàng)技能則需要耗費(fèi)一定的技能點(diǎn)數(shù)。只有學(xué)會了某一項(xiàng)技能以后，才能繼續(xù)學(xué)習(xí)它的后繼技能。每項(xiàng)技能又有著不同的級別，級別越高效果越好，而技能的升級也是需要耗費(fèi)技能點(diǎn)數(shù)的。有個玩家積攢了一定的技能點(diǎn)數(shù)，他想盡可能地利用這些技能點(diǎn)數(shù)來達(dá)到最好的效果。因此他給所有的級別都打上了分，他認(rèn)為效果越好的分?jǐn)?shù)也越高?，F(xiàn)在他要你幫忙尋找一個分配技能點(diǎn)數(shù)的方案，使得分?jǐn)?shù)總和最高。 Input該題有多組測試數(shù)據(jù)。 每組測試數(shù)據(jù)第一行是一個整數(shù)n（1=n=20）,表示所有不同技能的總數(shù)。 接下來依次給出n個不同技能的詳細(xì)情況。 每個技能描述包括5行。 第一行是該技能的名稱。 第2行是該技能在技能樹中父技能的名稱，名稱為None則表示該技能不需要任何的先修技能便能學(xué)習(xí)。 第3行是一個整數(shù)L（1=L=20），表示這項(xiàng)技能所能擁有的最高級別。 第4行共有L個整數(shù)，其中第I個整數(shù)表示從地I1級升到第I級所需要的技能點(diǎn)數(shù)（0級表示沒有學(xué)習(xí)過）。 第5行包括L個整數(shù)，其中第I個整數(shù)表示從第I1級升級到第I級的效果評分，分?jǐn)?shù)不超過20。 在技能描述之后，共有兩行，第1行是一個整數(shù)P，表示目前所擁有的技能點(diǎn)數(shù)。 接下來1行是N個整數(shù)，依次表示角色當(dāng)前習(xí)得的技能級別，0表示還未學(xué)習(xí)。這里不會出現(xiàn)非法情況。 Output每組測試數(shù)據(jù)只需輸出最佳分配方案所得的分?jǐn)?shù)總和。 Sample Input3Freezing ArrowIce Arrow3 3 3 3 15 4 6Ice ArrowCold Arrow24 310 17Cold ArrowNone33 3 215 5 2100 0 1Sample Output42Source解析：這題是選課的加強(qiáng)版，但并難不倒我們還是把一棵樹轉(zhuǎn)換為二叉樹，完后從子節(jié)點(diǎn)到根節(jié)點(diǎn)作一次dp，最后得到最優(yōu)解由于和上題很相像就不寫方程了。源代碼程序：program bluewater。typetree=record s,sf:string。 l,r,m:longint。 c:array[1..20] of longint。 d:array[1..20] of longint。 end。vari,j,k,l,m,n:longint。a:array[0..20] of tree。b:array[0..20] of longint。learn:array[0..20] of longint。f:array[0..20,0..8000] of longint。function treedp(x,y:longint):longint。 var i,j,k,l,max,o,p,q:longint。 begin if f[x,y]1 then begin treedp:=f[x,y]。exit。end。 max:=treedp(a[x].r,y)。 {learn0} if learn[x]0 then begin for k:=0 to y do begin i:=treedp(a[x].l,k)+treedp(a[x].r,yk)。 if imax then max:=i。 end。 end。 {learn=0} l:=0。p:=0。i:=0。 for o:=1 to a[x].m do begin if olearn[x] then begin l:=l+a[x].c[o]。p:=p+a[x].d[o]。end。 for k:=0 to yl do begin i:=treedp(a[x].l,k)+treedp(a[x].r,ylk)+p。 if imax then max:=i。 end。 end。 f[x,y]:=max。 treedp:=max。 end。function find(x:string):longint。 var i,j:longint。 begin for i:=0 to n do if a[i].s=x then break。 find:=i。 end。beginwhile not(eof(input)) dobegin{input}readln(n)。fillchar(a,sizeof(a),0)。fillchar(b,sizeof(b),0)。a[0].s:=39。None39。for i:=1 to n do with a[i] do begin readln(s)。 readln(sf)。 readln(m)。 for j:=1 to m do read(c[j])。readln。 for j:=1 to m do read(d[j])。readln。 end。readln(m)。if m8000 then m:=8000。for i:=1 to n do read(learn[i])。readln。{build binary tree}for i:=1 to n do begin k:=find(a[i].sf)。 if b[k]=0 then begin b[k]:=i。a[k].l:=i。end else begin a[b[k]].r:=i。b[k]:=i。end。 end。{bian jie}for i:=0 to 20 do for j:=0 to 8000 do f[i,j]:=1。for i:=0 to 8000 do f[0,i]:=0。{main}writeln(treedp(a[0].l,m))。end。end.戰(zhàn)略游戲ProblemBob喜歡玩電腦游戲，特別是戰(zhàn)略游戲。但是他經(jīng)常無法找到快速玩過游戲的辦法?，F(xiàn)在他有個問題。他要建立一個古城堡，城堡中的路形成一棵樹。他要在這棵樹的結(jié)點(diǎn)上放置最少數(shù)目的士兵，使得這些士兵能了望到所有的路。注意，某個士兵在一個結(jié)點(diǎn)上時，與該結(jié)點(diǎn)相連的所有邊將都可以被了望到。請你編一程序，給定一樹，幫Bob計(jì)算出他需要放置最少的士兵.Input第一行為一整數(shù)Ｍ，表示有Ｍ組測試數(shù)據(jù)每組測試數(shù)據(jù)表示一棵樹，描述如下：第一行 N，表示樹中結(jié)點(diǎn)的數(shù)目。第二行至第N+1行，每行描述每個結(jié)點(diǎn)信息，依次為：該結(jié)點(diǎn)標(biāo)號i，k(后面有k條邊與結(jié)點(diǎn)I相連)。接下來k個數(shù)，分別是每條邊的另一個結(jié)點(diǎn)標(biāo)號r1，r2，...，rk。 對于一個n(0n=1500)個結(jié)點(diǎn)的樹，結(jié)點(diǎn)標(biāo)號在0到n1之間，在輸入數(shù)據(jù)中每條邊只出現(xiàn)一次。 Output輸出文件僅包含一個數(shù)，為所求的最少的士兵數(shù)目。 例如，對于如下圖所示的樹： 答案為1（只要一個士兵在結(jié)點(diǎn)1上）。 Sample Input240 1 11 2 2 32 03 053 3 1 4 21 1 02 00 04 0Sample Output12Sourcesgoi 分析：這題有2種做法，一種是比較簡單但不是很嚴(yán)密的貪心，如果測試數(shù)據(jù)比較刁鉆的話就不可能ac，而這題是一道比較典型的樹型動態(tài)規(guī)劃的題目，這題不但要考慮子節(jié)點(diǎn)對他的根節(jié)點(diǎn)的影響，而且每放一個士兵，士兵所在位置既影響他的子節(jié)點(diǎn)也影響了他的根節(jié)點(diǎn)。不過狀態(tài)還是很容易來表示的，動規(guī)實(shí)現(xiàn)也不是很難，不過這在這些例題中也有了些“創(chuàng)新”了。而且這題不是一個對二叉樹的dp，而是對一顆普通樹的dp，所以更具代表性。源程序代碼：program bluewater。constmaxn=1500。vari,j,k,l:longint。m,n,p,q:longint。a:array[0..maxn,0..maxn] of boolean。b:array[0..maxn] of longint。c:array[0..maxn] of boolean。function leaf(x:longint):boolean。 var i,j:longint。 t:boolean。 begin t:=true。 for i:=0 to n1 do if a[x,i] then begin t:=false。break。end。 leaf:=t。 end。function treedp(x:longint):longint。 var i,j,k,l:longint。 begin j:=0。{add} k:=0。{leaf} l:=0。{not put not leaf} for i:=0 to n1 do if (a[x,i]) and (xi) then if leaf(i) then inc(k) else begin j:=j+treedp(i)。 if not(c[i]) then inc(l)。 end。 {puanduan} if (k0) or (l0) then begin c[x]:=true。treedp:=j+1。exit。end。 if (j0) and (l=0) then begin treedp:=j。exit。end。 end。begin{input}readln(m)。for p:=1 to m do begin fillchar(b,sizeof(b),0)。 fillchar(a,sizeof(a),false)。 fillchar(c,sizeof(c),false)。 readln(n)。 for i:=1 to n do begin read(k,l)。 for j:=1 to l do begin read(q)。 a[k,q]:=true。 b[q]:=1。 end。 readln。 end。 {main} for i:=0 to n1 do if b[i]=0 then break。 fillchar(b,sizeof(b),0)。 if leaf(i) then writeln(39。139。) else writeln(treedp(i))。 end。end.網(wǎng)絡(luò)收費(fèi)【問題描述】網(wǎng)絡(luò)已經(jīng)成為當(dāng)今世界不可或缺的一部分。每天都有數(shù)以億計(jì)的人使用網(wǎng)絡(luò) 進(jìn)行學(xué)習(xí)、科研、娛樂等活動。然而，不可忽視的一點(diǎn)就是網(wǎng)絡(luò)本身有著龐大的 運(yùn)行費(fèi)用。所以，向使用網(wǎng)絡(luò)的人進(jìn)行適當(dāng)?shù)氖召M(fèi)是必須的，也是合理的。 MY 市NS 中學(xué)就有著這樣一個教育網(wǎng)絡(luò)。網(wǎng)絡(luò)中的用戶一共有2N 個，編號 N 。這些用戶之間是用路由點(diǎn)和網(wǎng)線組成的。用戶、路由點(diǎn)與 依次為 1, 2, 3, …, 2 網(wǎng)線共同構(gòu)成一個滿二叉樹結(jié)構(gòu)。樹中的每一個葉子結(jié)點(diǎn)都是一個用戶，每一個 非葉子結(jié)點(diǎn)（灰色）都是一個路由點(diǎn)，而每一條邊都是一條網(wǎng)線（見下圖，用戶 結(jié)點(diǎn)中的數(shù)字為其編號）。 MY 網(wǎng)絡(luò)公司的網(wǎng)絡(luò)收費(fèi)方式比較奇特，稱為“ 配對收費(fèi) ”。即對于每兩個 用戶 i, j (1≤i j ≤2^N ) 進(jìn)行收費(fèi)。由于用戶可以自行選擇兩種付