三色二叉树 解题报告

问题描述

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

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

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

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

输入文件

输入文件名:TRO.IN

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

输出文件

输出文件名:TRO.OUT

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

样例输入 1122002010

样例输出 5 2

思路分析

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

对于一颗树,分为两种情况考虑:

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

题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名

当前页阅读量为: