三色二叉树

三色二叉树

---

Time Limit:1s	Memory limit:32M
Accepted Submit:81	Total Submit:211

---

一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”：

例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。

你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入输出格式

输入数据由多组数据组成。
每组数据仅有一行，不超过10000个字符，表示一个二叉树序列。

对于每组输入数据，输出仅一行包含两个整数，依次表示最多和最少有多少个点能够被染成绿色。

样例输入

1122002010

样例输出

5 2

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define top_num 2
#define min_top 0
#define max_top 1

#define is_green 0
#define no_green 1

#define MAX_NUM(x, y) ((x) > (y) ? (x) : (y))
#define MIN_NUM(x, y) ((x) < (y) ? (x) : (y))

int main()
{
    int i, len, top[top_num];
    int isa, noa, isb, nob;
    int min_num, max_num;
    int stack[top_num][2][10010];
    char *p, str[10010];

    while(scanf("%s", str) != EOF)
    {
        len = strlen(str);
        p = &str[len - 1];
        top[min_top] = top[max_top] = 0;
        for (i = 0; i < len; ++i, --p)
        {
            switch(*p)
            {
            case '0':
                stack[min_top][is_green][top[min_top]] = 1;
                stack[min_top][no_green][top[min_top]] = 0;
                ++top[min_top];

                stack[max_top][is_green][top[max_top]] = 1;
                stack[max_top][no_green][top[max_top]] = 0;
                ++top[max_top];
                break;
            case '1':
                --top[min_top];
                isa = stack[min_top][is_green][top[min_top]];
                noa = stack[min_top][no_green][top[min_top]];
                stack[min_top][is_green][top[min_top]] = noa + 1;
                stack[min_top][no_green][top[min_top]] = MIN_NUM(isa, noa);
                ++top[min_top];

                --top[max_top];
                isa = stack[max_top][is_green][top[max_top]];
                noa = stack[max_top][no_green][top[max_top]];
                stack[max_top][is_green][top[max_top]] = noa + 1;
                stack[max_top][no_green][top[max_top]] = MAX_NUM(isa, noa);
                ++top[max_top];
                break;
            case '2':
                --top[min_top];
                isa = stack[min_top][is_green][top[min_top]];
                noa = stack[min_top][no_green][top[min_top]];
                --top[min_top];
                isb = stack[min_top][is_green][top[min_top]];
                nob = stack[min_top][no_green][top[min_top]];
                stack[min_top][is_green][top[min_top]] = noa + nob + 1;
                stack[min_top][no_green][top[min_top]] = MIN_NUM(isa + nob, isb + noa);
                ++top[min_top];

                --top[max_top];
                isa = stack[max_top][is_green][top[max_top]];
                noa = stack[max_top][no_green][top[max_top]];
                --top[max_top];
                isb = stack[max_top][is_green][top[max_top]];
                nob = stack[max_top][no_green][top[max_top]];
                stack[max_top][is_green][top[max_top]] = noa + nob + 1;
                stack[max_top][no_green][top[max_top]] = MAX_NUM(isa + nob, isb + noa);
                ++top[max_top];
                break;
            default:
                break;
            }
        }

        --top[min_top];
        isa = stack[min_top][is_green][top[min_top]];
        noa = stack[min_top][no_green][top[min_top]];
        min_num = MIN_NUM(isa, noa);
        --top[max_top];
        isa = stack[max_top][is_green][top[max_top]];
        noa = stack[max_top][no_green][top[max_top]];
        max_num = MAX_NUM(isa, noa);

        printf("%d %d\n", max_num, min_num);
    }

    return 0;
}