【問題描述】
一棵二叉樹可以按照如下規(guī)則表示成一個由0、1、2 組成的字符序列，我們稱之為“二叉樹序列S”：
2表示該樹有兩個子節(jié)點， 和分別表示其兩個子樹的二叉樹序列
1表示該樹有一個子節(jié)點， 為其子樹的二叉樹序列
0表示該樹沒有子節(jié)點
你的任務(wù)是要對一棵二叉樹的節(jié)點進行染色。每個節(jié)點可以被染成紅色、綠色或藍色。并且，一個節(jié)點與其子節(jié)點的顏色必須不同，如果該節(jié)點有兩個子節(jié)點，那么這兩個子節(jié)點的顏色也必須不相同。給定一棵二叉樹的二叉樹序列，請求出這棵樹中最多和最少有多少個點能夠被染成綠色。
【輸入文件】
輸入文件名：TRO.IN
輸入文件僅有一行，不超過10000 個字符，表示一個二叉樹序列。
【輸出文件】
輸出文件名：TRO.OUT
輸出文件也只有一行，包含兩個數(shù)，依次表示最多和最少有多少個點能夠被
染成綠色。
【樣例輸入】
1122002010
【樣例輸出】
5 2
【分析】
1.動歸分析
拿最大來說。
每個節(jié)點的狀態(tài)只有三種顏色，我們用f[i][0],f[i][1]分別代表第i個點染綠色和不然綠色的最多的點數(shù)。因為如果一個點不染綠色，那么他染另兩種顏色是等價的。如此我們就得到了如下的動規(guī)方程：
- 葉子：f[i][0]=1; f[i][1]=0;
- 一個子節(jié)點：f[i][0]=f[子節(jié)點][1]; f[i][1]=max(f[子節(jié)點][0],f[子節(jié)點][1]);
- 兩個子節(jié)點：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.樹的確定
因為是一棵二叉樹的前序遍歷，那么對于一個有子節(jié)點的點來說，左兒子就是i+1。我們引進一個link[i]，表示以i為根的子樹最后一個點的標號，那么r[i]=link[l[i]]+1。
對于link[l]，我們?nèi)绱舜_定：
- 葉子：link[l]=l;
- 一個子節(jié)點：link[l]=link[l+1];
- 兩個子節(jié)點：link[l]=link[link[l+1]+1];
然后就是實現(xià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: