十二 14

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

POI Add comments206 views

首先是根据输入的前序遍历建树，然后树形动态规划，递归地建立二叉树。假设绿色为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即可。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

/* 
 * 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;
}

三色二叉树

问题描述

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

  • 0 该树没有子节点
  • 1S1 该树有一个子节点，S1为其二叉树序列
  • 1S1S2 该树有两个子节点，S1,S2分别为两个二叉树的序列

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

Image:Trot.gif

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

输入文件
输入文件仅有一行，不超过10000个字符，表示一个二叉树序列。

输出文件

输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

样例输入

1122002010

样例输出

5 2

相關日誌

标签：, , , ,


3 Responses to “POI 1999 三色二叉树 Three−coloring of binary trees”

  1. richeir Says:
    十二月 14th, 2008 at 21:57:34

    大哥，你一天写几个题啊~速度好快~
    顶你写题的速度~
    继续加油~
    有机会的话，明年的HAOI上见~

    [回复]

    CmYkRgB123 回复:
    十二月 16th, 2008 at 22:08:40

    貌似高三不能参加HAOI

    [回复]

  2. CmYkRgB123 Says:
    十二月 15th, 2008 at 12:58:36

    快吗？星期天我才写了3个题啊。够慢了

    哎，要不是因为玩仙剑四

    [回复]

Leave a Reply

43 queries. 0.603 seconds. Designed by NattyWP .
Images by desEXign.