加分二叉樹
問題描述
設壹個n個節點的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數字1,2,3,…,n為節點編號。每個節點都有壹個分數（均為正整數），記第i個節點的分數為di，tree及它的每個子樹都有壹個加分，任壹棵子樹subtree（也包含tree本身）的加分計算方法如下：
subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數
若某個子樹為空，規定其加分為1，葉子的加分就是葉節點本身的分數。不考慮它的空子樹。
試求壹棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；
（1）tree的最高加分
（2）tree的前序遍歷
[分析]很顯然，本題適合用動態規劃來解。如果用數組value[i,j]表示從節點i到節點j所組成的二叉樹的最大加分，則動態方程可以表示如下：
value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j], value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j,j], value[j,j]+value[i,j-1]}
題目還要求輸出最大加分樹的前序遍歷序列，因此必須在計算過程中記下從節點i到節點j所組成的最大加分二叉樹的根節點，用數組root[i,j]表示
Ural 1018 二*蘋果樹
題目
有壹棵蘋果樹，如果樹枝有分叉，壹定是分2叉（就是說沒有只有1個兒子的結點）
這棵樹***有N個結點（葉子點或者樹枝分叉點），編號為1-N,樹根編號壹定是1。
我們用壹根樹枝兩端連接的結點的編號來描述壹根樹枝的位置。下面是壹顆有4個樹枝的樹
2 5
\ /
3 4
\ /
1
現在這顆樹枝條太多了，需要剪枝。但是壹些樹枝上長有蘋果。
給定需要保留的樹枝數量，求出最多能留住多少蘋果。
輸入格式
第1行2個數，N和Q(1<=Q<= N,1<N<=100)。
N表示樹的結點數，Q表示要保留的樹枝數量。接下來N-1行描述樹枝的信息。
每行3個整數，前兩個是它連接的結點的編號。第3個數是這根樹枝上蘋果的數量。
每根樹枝上的蘋果不超過30000個。
輸出格式
壹個數，最多能留住的蘋果的數量。
解析：因為題目壹給出就是二叉的，所以很容易就可以寫出方程：
a(I,j):=max(a(i.left,k)+a(i.right,j-k)),0<=k<=j
源程序代碼：
由於比較簡單便不給完全的代碼了。
Function treedp(x,y:longint):longint;
Var I,j,k:longint;
Begin
J:=0;
For I:=0 to y do
begin
k:=treedp(b[x].l,I)+treedp(b[x].r,y-I);
if k>j then j:=k;
end;
treedp:=j;
End;
選課
[問題描述]
在大學裏每個學生，為了達到壹定的學分，必須從很多課程裏選擇壹些課程來學習，在課程裏有些課程必須在某些課程之前學習，如高等數學總是在其它課程之前學習。現在有N門功課，每門課有個學分，每門課有壹門或沒有直接先修課（若課程a是課程b的先修課即只有學完了課程a，才能學習課程b）。壹個學生要從這些課程裏選擇M門課程學習，問他能獲得的最大學分是多少？
輸入：
第壹行有兩個整數N,M用空格隔開。(1<=N<=200,1<=M<=150)
接下來的N行,第I+1行包含兩個整數ki和si, ki表示第I門課的直接先修課，si表示第I門課的學分。若ki=0表示沒有直接先修課（1<=ki<=N, 1<=si<=20）。
輸出：
只有壹行，選M門課程的最大得分。
樣例：
輸入：
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2 輸出：
13
解析：
這題比蘋果樹多了壹個步驟就是把壹棵普通樹轉化為二叉樹。
讀入數據時把二叉樹建好：第壹個孩子作為父節點的左子樹，其它孩子作為第壹個孩子的右子樹。
F（x，y）：表示節點x取y門課得最高學分，則
F（x，y）＝max（f（x.l,k-1）+x.v+f(x.r,y-k)）k=0,1,..y
f（x.l,k-1）+x.v(課程x的學分) :表示選了課程x,左孩子選k-1門課,***k門課。
f (x.r,y-k)表示右孩子只能選y-k門課。
標程中節點－1表示空節點，0是根節點，1—n是n門可選課程的節點.
思考:若本題加上選那些課程可得到這個最大學分,怎樣修改程序？
實現：
怎麽實現，是在競賽中的很重要的壹個問題，如果妳想ac了這道題目的話，妳應該熟悉怎麽把壹棵樹轉化成二叉樹，完後怎麽用遞規的思想來實現動態規劃。所以堅實的基礎是很重要的東西，如果沒有了基礎，什麽都是空中樓閣。
程序中已經邊讀邊把二叉樹建立好了。
源程序代碼：
program bluewater;
type
tree=record
l,r,k:longint;
end;
var
s:string;
i,j,k,l:longint;
n,m:longint;
a:array[0..200] of tree;
b:array[-1..200,0..150] of integer;
f:array[0..200] of longint;
procedure treedp(x,y:longint);
var i,j,k,l:longint;
begin
if b[x,y]>=0 then exit;
treedp(a[x].r,y);{只有右子樹的情況}
j:=b[a[x].r,y];
for k:=1 to y do{左右子樹都有的情況}
begin
treedp(a[x].l,k-1);
treedp(a[x].r,y-k);
i:=b[a[x].l,k-1]+b[a[x].r,y-k]+a[x].k;
if i>j then j:=i;
end;
b[x,y]:=j;
end;
begin
readln(s);
assign(input,s);reset(input);
readln(n,m);
fillchar(f,sizeof(f),0);
for i:=0 to n do
begin a[i].l:=-1;a[i].r:=-1;a[i].k:=-1;end;
{build tree}
for i:=1 to n do
begin
readln(k,l);
a[i].k:=l;
if f[k]=0 then a[k].l:=i
else a[f[k]].r:=i;
f[k]:=i;
end;
{bianjie}
for i:=-1 to n do
for j:=-1 to m do
if (i=-1) or (j=0) then b[i,j]:=0 else b[i,j]:=-1;
{tree dp}
treedp(a[0].l,m);
{output}
writeln(b[a[0].l,m]);
end.
Tju1053 技能樹
Problem
玩過Diablo的人對技能樹壹定是很熟悉的。壹顆技能樹的每個結點都是壹項技能，要學會這項技能則需要耗費壹定的技能點數。
只有學會了某壹項技能以後，才能繼續學習它的後繼技能。每項技能又有著不同的級別，級別越高效果越好，而技能的升級也是
需要耗費技能點數的。
有個玩家積攢了壹定的技能點數，他想盡可能地利用這些技能點數來達到最好的效果。因此他給所有的級別都打上了分，他認為
效果越好的分數也越高。現在他要妳幫忙尋找壹個分配技能點數的方案，使得分數總和最高。
Input
該題有多組測試數據。
每組測試數據第壹行是壹個整數n（1<=n<=20）,表示所有不同技能的總數。
接下來依次給出n個不同技能的詳細情況。
每個技能描述包括5行。
第壹行是該技能的名稱。
第2行是該技能在技能樹中父技能的名稱，名稱為None則表示該技能不需要任何的先修技能便能學習。
第3行是壹個整數L（1<=L<=20），表示這項技能所能擁有的最高級別。
第4行***有L個整數，其中第I個整數表示從地I-1級升到第I級所需要的技能點數（0級表示沒有學習過）。
第5行包括L個整數，其中第I個整數表示從第I-1級升級到第I級的效果評分，分數不超過20。
在技能描述之後，***有兩行，第1行是壹個整數P，表示目前所擁有的技能點數。
接下來1行是N個整數，依次表示角色當前習得的技能級別，0表示還未學習。這裏不會出現非法情況。
Output
每組測試數據只需輸出最佳分配方案所得的分數總和。
解析：這題是選課的加強版，但並難不倒我們
還是把壹棵樹轉換為二叉樹，完後從子節點到根節點作壹次dp，最後得到最優解
由於和上題很相像就不寫方程了。
源代碼程序：
program bluewater;
type
tree=record
s,sf:string;
l,r,m:longint;
c:array[1..20] of longint;
d:array[1..20] of longint;
end;
var
i,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);
{learn>0}
if learn[x]>0 then
begin
for k:=0 to y do
begin
i:=treedp(a[x].l,k)+treedp(a[x].r,y-k);
if i>max then max:=i;
end;
end;
{learn=0}
l:=0;p:=0;i:=0;
for o:=1 to a[x].m do
begin
if o>learn[x] then
begin l:=l+a[x].c[o];p:=p+a[x].d[o];end;
for k:=0 to y-l do
begin
i:=treedp(a[x].l,k)+treedp(a[x].r,y-l-k)+p;
if i>max 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;
begin
while not(eof(input)) do
begin
{input}
readln(n);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
a[0].s:='None';
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 m>8000 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.
戰略遊戲
Problem
Bob喜歡玩電腦遊戲，特別是戰略遊戲。但是他經常無法找到快速玩過遊戲的辦法。現在他有個問題。
他要建立壹個古城堡，城堡中的路形成壹棵樹。他要在這棵樹的結點上放置最少數目的士兵，使得這些士兵能了望到所有的路。
註意，某個士兵在壹個結點上時，與該結點相連的所有邊將都可以被了望到。
請妳編壹程序，給定壹樹，幫Bob計算出他需要放置最少的士兵.
Input
第壹行為壹整數M，表示有M組測試數據
每組測試數據表示壹棵樹，描述如下：
第壹行 N，表示樹中結點的數目。
第二行至第N+1行，每行描述每個結點信息，依次為：該結點標號i，k(後面有k條邊與結點I相連)。
接下來k個數，分別是每條邊的另壹個結點標號r1，r2，...，rk。
對於壹個n(0<n<=1500)個結點的樹，結點標號在0到n-1之間，在輸入數據中每條邊只出現壹次。
Output
輸出文件僅包含壹個數，為所求的最少的士兵數目。
例如，對於如下圖所示的樹：
答案為1（只要壹個士兵在結點1上）。
Sample Input
2
4
0 1 1
1 2 2 3
2 0
3 0
5
3 3 1 4 2
1 1 0
2 0
0 0
4 0
Sample Output
1
2
Source
sgoi
分析：這題有2種做法，壹種是比較簡單但不是很嚴密的貪心，如果測試數據比較刁鉆的話就不可能ac，而這題是壹道比較典型的樹型動態規劃的題目，這題不但要考慮子節點對他的根節點的影響，而且每放壹個士兵，士兵所在位置既影響他的子節點也影響了他的根節點。不過狀態還是很容易來表示的，動規實現也不是很難，不過這在這些例題中也有了些“創新”了。而且這題不是壹個對二叉樹的dp，而是對壹顆普通樹的dp，所以更具代表性。
源程序代碼：
program bluewater;
const
maxn=1500;
var
i,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 n-1 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 n-1 do
if (a[x,i]) and (x<>i) then
if leaf(i) then inc(k) else
begin
j:=j+treedp(i);
if not(c[i]) then inc(l);
end;
{puanduan}
if (k>0) or (l>0) then begin c[x]:=true;treedp:=j+1;exit;end;
if (j>0) 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 n-1 do
if b[i]=0 then break;
fillchar(b,sizeof(b),0);
if leaf(i) then writeln('1') else writeln(treedp(i));
end;
end.
Ural 1039 沒有上司的晚會
背景
有個公司要舉行壹場晚會。
為了能玩得開心，公司領導決定：如果邀請了某個人，那麽壹定不會邀請他的上司
（上司的上司，上司的上司的上司……都可以邀請）。
題目
每個參加晚會的人都能為晚會增添壹些氣氛，求壹個邀請方案，使氣氛值的和最大。
輸入格式
第1行壹個整數N（1<=N<=6000）表示公司的人數。
接下來N行每行壹個整數。第i行的數表示第i個人的氣氛值x(-128<=x<=127)。
接下來每行兩個整數L，K。表示第K個人是第L個人的上司。
輸入以0 0結束。
輸出格式
壹個數，最大的氣氛值和。
樣例輸入
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
樣例輸出
5
http://acm.timus.ru/submit.aspx?space=1&num=1039
分析：
f[i,1]表示邀請i的最大值
f[i,2]表示不邀請i的最大值
f[i,1]=sigma(f[i.sons,2])
f[i,2]=sigma(max{f[i.sons,1],f[i.sons,2]})
這個又是樹型動態規劃的壹種分類，每個結點都有二種狀態既選與不選。 .
我的教程裏粘貼來的。