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
```

上次修改时间 2017-05-22

相关日志