【問(wèn)題描述】
一棵二叉樹(shù)可以按照如下規(guī)則表示成一個(gè)由0、1、2 組成的字符序列，我們稱(chēng)之為“二叉樹(shù)序列S”：
2表示該樹(shù)有兩個(gè)子節(jié)點(diǎn)， 和分別表示其兩個(gè)子樹(shù)的二叉樹(shù)序列
1表示該樹(shù)有一個(gè)子節(jié)點(diǎn)， 為其子樹(shù)的二叉樹(shù)序列
0表示該樹(shù)沒(méi)有子節(jié)點(diǎn)
你的任務(wù)是要對(duì)一棵二叉樹(shù)的節(jié)點(diǎn)進(jìn)行染色。每個(gè)節(jié)點(diǎn)可以被染成紅色、綠色或藍(lán)色。并且，一個(gè)節(jié)點(diǎn)與其子節(jié)點(diǎn)的顏色必須不同，如果該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，那么這兩個(gè)子節(jié)點(diǎn)的顏色也必須不相同。給定一棵二叉樹(shù)的二叉樹(shù)序列，請(qǐng)求出這棵樹(shù)中最多和最少有多少個(gè)點(diǎn)能夠被染成綠色。
【輸入文件】
輸入文件名：TRO.IN
輸入文件僅有一行，不超過(guò)10000 個(gè)字符，表示一個(gè)二叉樹(shù)序列。
【輸出文件】
輸出文件名：TRO.OUT
輸出文件也只有一行，包含兩個(gè)數(shù)，依次表示最多和最少有多少個(gè)點(diǎn)能夠被
染成綠色。
【樣例輸入】
1122002010
【樣例輸出】
5 2
【分析】
1.動(dòng)歸分析
拿最大來(lái)說(shuō)。
每個(gè)節(jié)點(diǎn)的狀態(tài)只有三種顏色，我們用f[i][0],f[i][1]分別代表第i個(gè)點(diǎn)染綠色和不然綠色的最多的點(diǎn)數(shù)。因?yàn)槿绻粋€(gè)點(diǎn)不染綠色，那么他染另兩種顏色是等價(jià)的。如此我們就得到了如下的動(dòng)規(guī)方程：
- 葉子：f[i][0]=1; f[i][1]=0;
- 一個(gè)子節(jié)點(diǎn)：f[i][0]=f[子節(jié)點(diǎn)][1]; f[i][1]=max(f[子節(jié)點(diǎn)][0],f[子節(jié)點(diǎn)][1]);
- 兩個(gè)子節(jié)點(diǎn)：f[i][0]=f[左兒子][1]+f[右兒子][1]; f[i][1]=max(f[左兒子][1]+f[右兒子][0],f[左兒子][0]+f[右兒子][1]);
最后輸出就是max(f[0][1],f[0][0])。
最小的和最大的相同。
2.樹(shù)的確定
因?yàn)槭且豢枚鏄?shù)的前序遍歷，那么對(duì)于一個(gè)有子節(jié)點(diǎn)的點(diǎn)來(lái)說(shuō)，左兒子就是i+1。我們引進(jìn)一個(gè)link[i]，表示以i為根的子樹(shù)最后一個(gè)點(diǎn)的標(biāo)號(hào)，那么r[i]=link[l[i]]+1。
對(duì)于link[l]，我們?nèi)绱舜_定：
- 葉子：link[l]=l;
- 一個(gè)子節(jié)點(diǎn)：link[l]=link[l+1];
- 兩個(gè)子節(jié)點(diǎn)：link[l]=link[link[l+1]+1];
然后就是實(shí)現(xiàn)了。因?yàn)樽约号眠€是不是很熟，打了兩節(jié)課。
1: #include <stdio.h>
2: #include <string.h>
3: #include <iostream>
4: #define maxn 10010
5: #define MAXINT 10000000
6: using namespace std;
7:
8: char s[maxn];
9: int f[maxn][2];
10: int link[maxn];
11: int n;
12: int l[maxn],r[maxn];
13:
14: int _find(int x)
15: {
16: if (link[x]) return link[x];
17: if (s[x]=='0') link[x]=x;
18: else
19: if (s[x]=='1') link[x]=_find(x+1);
20: else
21: link[x]=_find(_find(x+1)+1);
22: return link[x];
23: }
24:
25: void find1(int x)
26: {
27: if (f[x][0]) return;
28: if (s[x]=='0')
29: {
30: f[x][0]=1;
31: f[x][1]=0;
32: }
33: else
34: if (s[x]=='1')
35: {
36: find1(l[x]);
37: f[x][0]=f[l[x]][1]+1;
38: f[x][1]=max(f[l[x]][1],f[l[x]][0]);
39: }
40: else
41: {
42: find1(l[x]);
43: find1(r[x]);
44: f[x][0]=f[l[x]][1]+f[r[x]][1]+1;
45: f[x][1]=max(f[l[x]][1]+f[r[x]][0],f[l[x]][0]+f[r[x]][1]);
46: }
47: }
48:
49: void find2(int x)
50: {
51: if (f[x][0]<MAXINT) return;
52: if (s[x]=='0')
53: {
54: f[x][0]=1;
55: f[x][1]=0;
56: }
57: else
58: if (s[x]=='1')
59: {
60: find2(l[x]);
61: f[x][0]=f[l[x]][1]+1;
62: f[x][1]=min(f[l[x]][1],f[l[x]][0]);
63: }
64: else
65: {
66: find2(l[x]);
67: find2(r[x]);
68: f[x][0]=f[l[x]][1]+f[r[x]][1]+1;
69: f[x][1]=min(f[l[x]][1]+f[r[x]][0],f[l[x]][0]+f[r[x]][1]);
70: }
71: }
72:
73: int main()
74: {
75: freopen("tro.in","r",stdin);
76: freopen("tro.out","w",stdout);
77:
78: scanf("%s",s);
79: n=strlen(s);
80: _find(0);
81: for (int i=0;i<n;++i)
82: {
83: l[i]=i+1;
84: r[i]=link[l[i]]+1;
85: }
86: find1(0);
87: printf("%d ",max(f[0][0],f[0][1]));
88: for (int i=0;i<n;++i)
89: f[i][0]=f[i][1]=MAXINT;
90: find2(0);
91: printf("%d\n",min(f[0][0],f[0][1]));
92: return 0;
93: }
94: