三色二叉樹 解題報告
問題描述
一棵二叉樹可以按照如下規則表示成一個由0、1、2組成的字符序列，我們稱之為「二叉樹序列S」。
例如，下圖所表示的二叉樹可以用二叉樹序列S=21200110來表示。
你的任務是要對一棵二叉樹的節點進行染色。每個節點可以被染成紅色、綠色或藍色。並且，一個節點與其子節點的顏色必須不同，如果該節點有兩個子節點，那麼這兩個子節點的顏色也必須不相同。
給定一棵二叉樹的二叉樹序列，請求出這棵樹中最多和最少有多少個點能夠被染成綠色。
輸入文件
輸入文件名：TRO.IN
輸入文件僅有一行，不超過10000個字符，表示一個二叉樹序列。
輸出文件
輸出文件名：TRO.OUT
輸出文件也只有一行，包含兩個數，依次表示最多和最少有多少個點能夠被染成綠色。
樣例輸入 1122002010
樣例輸出 5 2
思路分析
簡單的樹形動態規劃。這三種顏色是平級的。所謂多少個點能夠被染成綠色，其實染成什麼色都一樣。
對於一顆樹，分為兩種情況考慮：
- 父親染成綠色，則數量為兩個子樹不染成綠色的數量之和＋1。
- 父親不染成綠色，則數量為兩個子樹一個染成綠色，另一個不染成綠色的數量之和的最大值或最小值。
這個題目的建樹過程也需要注意。
完整代碼
//By Ceeji
//Date: 2009-3-12
//HAOI test 2 - Problem 2
//Type: Tree DP
//State: Accepted
Program tro;
Type node=record
l,r:longint;
end;
Var str:ansistring;
ch:char;
i,j,k,len,n,key,nn:longint;
a:array[1..30000]of node; // tree
dp:array[1..30000,1..4]of longint; //1: has green 2:not has green
b:array[1..30000]of boolean;
Function max(i,j:longint):longint;
begin
if i>j then exit(i) else exit(j);
end;
Function min(i,j:longint):longint;
begin
if i<j then exit(i) else exit(j);
end;
Procedure maketree(j:longint);
var c:char;
begin
c:=str[n];
if c='0' then
begin
exit;
end;
if c='1' then
begin
inc(n);
a[j].l:=n;
a[j].r:=0;
maketree(n);
exit;
end;
if c='2' then
begin
inc(n);
a[j].l:=n;
maketree(n);
inc(n);
a[j].r:=n;
maketree(n);
end;
end;
Procedure work(i:longint);
begin
if b[i] then exit;
b[i]:=true;
if a[i].l=0 then begin dp[i,1]:=0; dp[i,2]:=1; dp[i,3]:=0; dp[i,4]:=1; exit; end
else begin
work(a[i].l);
if a[i].r<>0 then work(a[i].r);
dp[i,1]:=max(dp[a[i].l,2]+dp[a[i].r,1],dp[a[i].l,1]+dp[a[i].r,2]);
dp[i,2]:=dp[a[i].l,1]+dp[a[i].r,1]+1;
dp[i,3]:=min(dp[a[i].l,3]+dp[a[i].r,4],dp[a[i].l,4]+dp[a[i].r,3]);
dp[i,4]:=dp[a[i].l,3]+dp[a[i].r,3]+1;
end;
end;
begin
assign(input,'tro.in'); reset(input);
assign(output,'tro.out'); rewrite(output);
readln(str);
fillchar(a,sizeof(a),0);
fillchar(dp,sizeof(dp),0);
len:=length(str);
n:=1; key:=1;
maketree(1);
str:='';
work(1);
writeln(max(dp[1,1],dp[1,2]),' ',min(dp[1,3],dp[1,4]));
close(output);
end.
© 轉載需附帶本文連結，依 CC BY-NC-SA 4.0 釋出。