Piano 3

题目描述

Takahashi 有一架排列成一行的 $100$ 个琴键。 从左数第 $i$ 个琴键称为琴键 $i$。 他将通过依次按下 $N$ 次琴键来演奏音乐。 在第 $i$ 次按键时，他会按下琴键 $A_i$，如果 $S_i= L$ 则用左手，如果 $S_i= R$ 则用右手。 在开始演奏之前，他可以把两只手放在任意他喜欢的琴键上，此时他的疲劳值为 0。 在演奏过程中，如果他将一只手从琴键 $x$ 移动到琴键 $y$，疲劳值会增加 $|y-x|$（反之，疲劳值不会因除移动手以外的任何原因而增加）。 要用某只手按下某个琴键，该手必须放在该琴键上。 找出演奏结束时可能的最小疲劳值。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $S_1$ $A_2$ $S_2$ $\vdots$ $A_N$ $S_N$

输出格式

输出演奏结束时的最小疲劳值。

4
3 L
6 R
9 L
1 R

11

3
2 L
2 L
100 L

98

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

188

提示

$1 \leq N \leq 100$ $1 \leq A_i \leq 100$ $N$ 和 $A_i$ 为整数。 $S_i$ 为 $L$ 或 $R$。例如，演奏可以如下进行：

最初，将左手放在琴键 $3$，右手放在琴键 $6$。 用左手按下琴键 $3$。 用右手按下琴键 $6$。 将左手从琴键 $3$ 移动到琴键 $9$。疲劳值增加了 $|9-3| = 6$。 将右手从琴键 $6$ 移动到琴键 $1$。疲劳值增加了 $|1-6| = 5$。 用左手按下琴键 $9$。 用右手按下琴键 $1$。

在这种情况下，演奏结束时的疲劳值为 $6+5 = 11$，这是可能的最小值。

标签: AtCoder|abc369B

来源

AtCoder|abc369B