POI 1999 三色二叉树 Three−coloring of binary trees
This post is written in Chinese. Please consider using Google Translate
首先是根据输入的前序遍历建树，然后树形动态规划，递归地建立二叉树。假设绿色为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
