POI 1999 三色二叉樹 Three−coloring of binary trees

首先是根據輸入的前序遍歷建樹，然後樹形動態規劃，遞歸地建立二叉樹。假設綠色爲0，紅色爲1，藍色爲2。要求兩遍動態規劃。

以最大值爲例，動態規劃狀態設定

F[i,c] 以節點i爲根的子樹中，根的顏色爲c時，這棵子樹上顏色爲0的節點的個數。

狀態轉移方程

如果i爲葉節點

F[i,c]=1 (c爲0)
F[i,c]=0 (c不爲0)

如果i只有一個子節點

F[i,0]=Max { F[i.left,1] , F[i.left,2] } + 1
F[i,1]=Max { F[i.left,0] , F[i.left,2] }
F[i,2]=Max { F[i.left,0] , F[i.left,1] }

如果i有兩個子節點

F[i,0]=Max { F[i,left,1]+F[i.right,2] , F[i,left,2]+F[i.right,1] } + 1
F[i,1]=Max { F[i,left,0]+F[i.right,2] , F[i,left,2]+F[i.right,0] }
F[i,2]=Max { F[i,left,0]+F[i.right,1] , F[i,left,1]+F[i.right,0] }

目標狀態

Max{ F[root,0] , F[root,1] , F[root,2] } (root爲根)

以上爲求最大值，求最小值方法一樣，把Max全部改成Min即可。

/* 
 * Problem: POI1999 trot
 * Author: Guo Jiabao
 * Time: 2008.12.14 17:09:22
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=10002;
const int INF=0x7FFFFFFF;

class node
{
    public:
        int c,p;
        node *l,*r;
        node() : l(0),r(0){}
};

char S[MAX];
node E[MAX],*root;
int L,N,Q,Ans1,Ans2;
int F[MAX][3];
bool (*compare)(int,int);

bool bigger(int a,int b) { return a>b; }
bool smaller(int a,int b) { return a<b; }

void build(node *P)
{
    Q++;
    int k=S[Q]-'0';
    P->c=k;
    if (k)
    {
        N++;
        P->l=&E[N];
        E[N].p=N;
        build(P->l);
        if (k==2)
        {
            N++;
            P->r=&E[N];
            E[N].p=N;
            build(P->r);
        }
    }
}

void init()
{
    freopen("trot.in","r",stdin);
    freopen("trot.out","w",stdout);
    scanf("%s",S);
    E[N=1].p=1;    Q=-1;
    root=&E[1];
    build(root);
}

int dp(node *P,int C)
{
    int L,R;
    if (P->c==0) //leaf
    {
        if (C==0)
            return 1;
        else
            return 0;
    }
    else if (P->c==1) //link
    {
        L=P->l->p;
        if (F[L][0]==-1)
            F[L][0]=dp(P->l,0);
        if (F[L][1]==-1)
            F[L][1]=dp(P->l,1);
        if (F[L][2]==-1)
            F[L][2]=dp(P->l,2);
        if (C==0)
        {
            if (compare(F[L][1] , F[L][2]))
                return F[L][1] + 1;
            else
                return F[L][2] + 1;
        }
        else if (C==1)
        {
            if (compare(F[L][0] , F[L][2]))
                return F[L][0];
            else
                return F[L][2];
        }
        else
        {
            if (compare(F[L][0] , F[L][1]))
                return F[L][0];
            else
                return F[L][1];
        }
    }
    else
    {
        L=P->l->p; R=P->r->p;
        if (F[L][0]==-1)
            F[L][0]=dp(P->l,0);
        if (F[L][1]==-1)
            F[L][1]=dp(P->l,1);
        if (F[L][2]==-1)
            F[L][2]=dp(P->l,2);
        if (F[R][0]==-1)
            F[R][0]=dp(P->r,0);
        if (F[R][1]==-1)
            F[R][1]=dp(P->r,1);
        if (F[R][2]==-1)
            F[R][2]=dp(P->r,2);
        if (C==0)
        {
            if (compare(F[L][1]+F[R][2] , F[L][2]+F[R][1]))
                return F[L][1]+F[R][2] + 1;
            else
                return F[L][2]+F[R][1] + 1;
        }
        else if (C==1)
        {
            if (compare(F[L][0]+F[R][2] , F[L][2]+F[R][0]))
                return F[L][0]+F[R][2];
            else
                return F[L][2]+F[R][0];
        }
        else
        {
            if (compare(F[L][0]+F[R][1] , F[L][1]+F[R][0]))
                return F[L][0]+F[R][1];
            else
                return F[L][1]+F[R][0];
        }
    }
}

void rin()
{
    int i;
    for (i=1;i<=N;i++)
        F[i][0]=F[i][1]=F[i][2]=-1;
}

void solve()
{
    Ans1=0;Ans2=INF;
    rin();
    compare=bigger;
    F[1][0]=dp(root,0);if (F[1][0] > Ans1) Ans1=F[1][0];
    F[1][1]=dp(root,1);if (F[1][1] > Ans1) Ans1=F[1][1];
    F[1][2]=dp(root,2);if (F[1][2] > Ans1) Ans1=F[1][2];
    rin();
    compare=smaller;
    F[1][0]=dp(root,0);if (F[1][0] < Ans2) Ans2=F[1][0];
    F[1][1]=dp(root,1);if (F[1][1] < Ans2) Ans2=F[1][1];
    F[1][2]=dp(root,2);if (F[1][2] < Ans2) Ans2=F[1][2];
}

int main()
{
    init();
    solve();
    printf("%d %d",Ans1,Ans2);
    return 0;
}

<h2><span class="mw-headline">三色二叉樹</span></h2>

問題描述

一棵二叉樹可以按照如下規則表示成一個由0、1、2組成的字符序列，我們稱之爲“二叉樹序列S”：

0 該樹沒有子節點
1S1 該樹有一個子節點，S1爲其二叉樹序列
1S1S2 該樹有兩個子節點，S1,S2分別爲兩個二叉樹的序列

例如，下圖所表示的二叉樹可以用二叉樹序列S=21200110來表示。

你的任務是要對一棵二叉樹的節點進行染色。每個節點可以被染成紅色、綠色或藍色。並且，一個節點與其子節點的顏色必須不同，如果該節點有兩個子節點，那麼這兩個子節點的顏色也必須不相同。給定一棵二叉樹的二叉樹序列，請求出這棵樹中最多和最少有多少個點能夠被染成綠色。

輸入文件輸入文件僅有一行，不超過10000個字符，表示一個二叉樹序列。

輸出文件

輸出文件也只有一行，包含兩個數，依次表示最多和最少有多少個點能夠被染成綠色。

樣例輸入
```
1122002010
```
樣例輸出
```
5 2
```

相關日誌