#P5597. 【XR-4】复读

【XR-4】复读

题目背景

赛时提醒:当机器人在这棵完全二叉树的根时,执行 U 是非法的,即你需要保证不可能出现这种情况。

赛时提醒:这棵二叉树是无限向下延伸的,即所有节点均有左子节点与右子节点,除了根的所有节点均有父亲。

题目描述

小 X 捡到了一台复读机,这台复读机可以向机器人发号施令。机器人将站在一棵完全二叉树的根上,完全二叉树是无限延伸的。你将向复读机录入一串指令,这串指令单个字符可以是:

  • L:命令机器人向当前节点的左子走;
  • R:命令机器人向当前节点的右子走;
  • U:命令机器人向当前节点的父亲走(若没有,则命令非法)。

录入指令后,复读机将会把指令无限复读下去。比如命令为 LR,那么机器人会遵从 LRLRLRLR... 一直走下去。

这棵完全二叉树上有一个 nn 个节点的连通块,保证这个连通块包含根节点。连通块上的每个节点都埋有宝藏,机器人到达过的地方如果有宝藏,则会将其开采。如果一个地方没有宝藏,机器人也可以到那里去。机器人也可以反复经过一个地方。

显然,这个连通块本身也是一棵二叉树。

现在,有人告诉了小 X 埋有宝藏的这棵二叉树的前序遍历,小 X 需要寻找到一条尽量短的指令,使得机器人能够挖掘出所有宝藏。

输入格式

一行一个字符串,由 0123 中的字符组成,表示埋有宝藏的这棵二叉树的前序遍历。

  • 0:表示这是一个没有儿子的节点。
  • 1:表示这是一个只有左子的节点。
  • 2:表示这是一个只有右子的节点。
  • 3:表示这是一个既有左子又有右子的节点。

输出格式

一个整数,表示最短指令的长度。

1313000

3

333003003300300

15

提示

【样例 1 说明】

一种可行的最短指令为 LRU


本题采用捆绑测试。

  • Subtask 1(31 points):2n102 \le n \le 10
  • Subtask 2(32 points):2n2002 \le n \le 200
  • Subtask 3(37 points):无特殊限制。

对于 100%100\% 的数据,2n2×1032 \le n \le 2 \times 10^3