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

本文正體字版由OpenCC轉換

首先是根據輸入的前序遍歷建樹，然後樹形動態規劃，遞歸地建立二叉樹。假設綠色爲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
```

上次修改時間 2017-05-22

相關日誌