分数: 400 点
问题陈述
Skenu 建造了一座建筑物, N 楼层。该大楼设有电梯,每层都停靠。
电梯有控制按钮,但斯肯努粗心地只在每一层楼安装了一个按钮——上行或下行。
这意味着,从每一层楼,一个人只能朝一个方向前进。
如果 S_i is U,仅安装“向上”按钮 i第1层只能上去;如果 S_i is D,仅安装“向下”按钮 i第1层只能下去。
必要时,居民只能通过其他楼层前往目的地楼层。 求两层楼所有有序对中下列数字的总和 (i,j):最少需要乘坐电梯多少次才能到达 j楼从 i楼。
约束
- 2 ≤ |S| ≤ 10^5
- S_i 是
UorD. - S_1 is
U. - S_{|S|} is
D.
输入
输入由标准输入按以下格式给出:
S_1S_2...S_{|S|}
输出
打印两层楼所有有序对上以下数字的总和 (i,j):最少需要乘坐电梯多少次才能到达 j楼从 i楼。
示例输入 1
UUD
示例输出 1
7
来自 1-st 楼,可以到达 2乘电梯一次到二楼。
来自 1-st 楼,可以到达 3- 乘电梯一次。
来自 2-二楼,可以到达 1乘电梯两次到一楼。
来自 2-二楼,可以到达 3- 乘电梯一次。
来自 3-rd楼,可以到达 1乘坐电梯一次。
来自 3-rd楼,可以到达 2乘电梯一次到二楼。
这些次数的总和, 7,应打印。
示例输入 2
UUDUUDUD
示例输出 2
77