本解题报告的版权归 Ceeji 所有，转载请注明并保留本注释。 问题描述 一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”： 例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。 你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。
输入文件 输入文件名：TRO.IN 输入文件仅有一行，不超过10000个字符，表示一个二叉树序列。
输出文件 输出文件名：TRO.OUT 输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
样例输入 1122002010
样例输出 5 2 思路分析 本解题报告的版权归 Ceeji 所有，转载请注明并保留本注释。 简单的树形动态规划。这三种颜色是平级的。所谓多少个点能够被染成绿色，其实染成什么色都一样。对于一颗树，分为两种情况考虑：1、父亲染成绿色，则数 量为两个子树不染成绿色的数量之和＋1。2、父亲不染成绿色，则数量为两个子树一个染成绿色，另一个不染成绿色的数量之和的最大值或最小值。 这个题目的建树过程也需要注意。
完整代码
//By Ceeji //Date: 2009-3-12 //HAOI test 2 - Problem 2 //Type: Tree DP //State: Accepted Program tro; Type node=record l,r:longint; end; Var str:ansistring; ch:char; i,j,k,len,n,key,nn:longint; a:array[1..30000]of node; // tree dp:array[1..30000,1..4]of longint; //1: has green 2:not has green b:array[1..30000]of boolean; Function max(i,j:longint):longint; begin if i>j then exit(i) else exit(j); end; Function min(i,j:longint):longint; begin if i<j then exit(i) else exit(j); end; Procedure maketree(j:longint); var c:char; begin c:=str[n]; if c=’0′ then [...]
近期评论