/ Vijos / 题库 /

描述

这里的堆是一个无限大的二叉树,它具有性质:
每一个结点有且仅有两个子节点:左、右子节点;
每个结点都有个数字标号。根节点标号为1;
如果一个结点的标号为X,则它的左子节点标号为2*X,右子节点标号为2*X+1。

一次在堆上的行走由根出发,经过多次步骤组成,每个步骤用一个字母表示:'L'或'R'或'P'。

'L'表示跳到左子节点;
'R'表示跳到右子节点;
'P'表示暂停一次;

行走结束时,最后所停在的节点上的标号就是这次行走的价值。比如:行走LR的价值是5、RPP的价值是3。

一类行走的集合可以用字符'L','R','P'或'*'组成的字符串表示,一个'*'字符表示这次步骤有'L','R'或'P'三种选择。这个集合由所有可能的行走组成。比如:
集合:L*R,包括3个行走:LLR,LRR和LPR。

集合:**,包括:LL,LR,LP,RL,RR,RP,PL,PR,PP。

现在要求出给定的一个集合中,所有可能行走的价值之和。

格式

输入格式

一个长度不超过10000的字符串,仅由'L','R','P'和'*'4种字符组成。

输出格式

要求的价值和。

样例1

样例输入1

L*R

样例输出1

25

样例2

样例输入2

**

样例输出2

33

限制

各个测试点1s

提示

50%的输入数据中,'*'不超过3个。

来源

2009芜湖市集训队

信息

ID
1522
难度
7
分类
动态规划 | 高精度 点击显示
标签
(无)
递交数
558
已通过
105
通过率
19%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库