【问题描述】
一棵二叉树可以按照如下规则表示成一个由0、1、2 组成的字符序列，我们称之为“二叉树序列S”：
2表示该树有两个子节点， 和分别表示其两个子树的二叉树序列
1表示该树有一个子节点， 为其子树的二叉树序列
0表示该树没有子节点
你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。
【输入文件】
输入文件名：TRO.IN
输入文件仅有一行，不超过10000 个字符，表示一个二叉树序列。
【输出文件】
输出文件名：TRO.OUT
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被
染成绿色。
【样例输入】
1122002010
【样例输出】
5 2
【分析】
1.动归分析
拿最大来说。
每个节点的状态只有三种颜色，我们用f[i][0],f[i][1]分别代表第i个点染绿色和不然绿色的最多的点数。因为如果一个点不染绿色，那么他染另两种颜色是等价的。如此我们就得到了如下的动规方程：
- 叶子：f[i][0]=1; f[i][1]=0;
- 一个子节点：f[i][0]=f[子节点][1]; f[i][1]=max(f[子节点][0],f[子节点][1]);
- 两个子节点：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.树的确定
因为是一棵二叉树的前序遍历，那么对于一个有子节点的点来说，左儿子就是i+1。我们引进一个link[i]，表示以i为根的子树最后一个点的标号，那么r[i]=link[l[i]]+1。
对于link[l]，我们如此确定：
- 叶子：link[l]=l;
- 一个子节点：link[l]=link[l+1];
- 两个子节点：link[l]=link[link[l+1]+1];
然后就是实现了。因为自己弄得还是不是很熟，打了两节课。
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: