三色二叉树解题报告 | 宁心勉学，慎思笃行

问题描述

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

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

你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。

给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入文件

输入文件名：TRO.IN

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

输出文件

输出文件名：TRO.OUT

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

样例输入 1122002010

样例输出 5 2

思路分析

简单的树形动态规划。这三种颜色是平级的。所谓多少个点能够被染成绿色，其实染成什么色都一样。

对于一颗树，分为两种情况考虑：

父亲染成绿色，则数量为两个子树不染成绿色的数量之和＋1。
父亲不染成绿色，则数量为两个子树一个染成绿色，另一个不染成绿色的数量之和的最大值或最小值。

这个题目的建树过程也需要注意。

完整代码

//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 
    begin 
       exit; 
    end; 
    if c='1' then 
    begin 
       inc(n); 
       a[j].l:=n; 
       a[j].r:=0; 
       maketree(n); 
       exit; 
    end; 
    if c='2' then 
    begin 
       inc(n); 
       a[j].l:=n; 
       maketree(n); 
       inc(n); 
       a[j].r:=n; 
       maketree(n); 
    end; 
end; 

Procedure work(i:longint); 
begin 
    if b[i] then exit; 
    b[i]:=true; 
    if a[i].l=0 then begin dp[i,1]:=0; dp[i,2]:=1; dp[i,3]:=0; dp[i,4]:=1; exit; end 
    else begin 
        work(a[i].l); 
        if a[i].r<>0 then work(a[i].r); 
        dp[i,1]:=max(dp[a[i].l,2]+dp[a[i].r,1],dp[a[i].l,1]+dp[a[i].r,2]); 
        dp[i,2]:=dp[a[i].l,1]+dp[a[i].r,1]+1; 
        dp[i,3]:=min(dp[a[i].l,3]+dp[a[i].r,4],dp[a[i].l,4]+dp[a[i].r,3]); 
        dp[i,4]:=dp[a[i].l,3]+dp[a[i].r,3]+1; 
    end; 
end;

begin 
    assign(input,'tro.in');    reset(input); 
    assign(output,'tro.out');  rewrite(output); 
    readln(str); 
    fillchar(a,sizeof(a),0); 
    fillchar(dp,sizeof(dp),0); 
    len:=length(str); 
    n:=1; key:=1; 
    maketree(1); 
    str:=''; 
    work(1); 
    writeln(max(dp[1,1],dp[1,2]),' ',min(dp[1,3],dp[1,4])); 
    close(output); 
end.

本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。

问题描述

思路分析

完整代码

猜你喜欢