← 返回题目列表

AtCoder · agc015_b

B. 电梯

中文机器翻译题面 查看原题

分数: 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 是 U or D.
  • 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