P13361 [GCJ 2011 Qualification] Bot Trust

Blue 和 Orange 是两台友好的机器人。一个邪恶的电脑主谋把它们分别关在不同的走廊里进行测试，之后可能会给它们蛋糕。 每条走廊里都有 $100$ 个按钮，编号为正整数 $\{1, 2, \ldots, 100\}$。按钮 $k$ 总是在距离走廊起点 $k$ 米的位置，两个机器人都从按钮 $1$ 开始。在一秒钟内，机器人可以向任意方向走一米，或者按下当前位置的按钮一次，或者停在当前位置不按按钮。为了完成测试，机器人需要按照给定顺序依次按下某些按钮。两个机器人都提前知道完整的按钮序列。请问它们最少需要多少秒才能完成任务？ 例如，考虑如下按钮序列： O $2$, B $1$, B $2$, O $4$ 这里，O $2$ 表示 Orange 走廊上的按钮 $2$，B $1$ 表示 Blue 走廊上的按钮 $1$，以此类推。机器人可以用如下策略在 $6$ 秒内完成按钮序列： | 时间 | Orange | Blue | | --- | --- | --- | | $1$ | 移动到按钮 $2$ | 停在按钮 $1$ | | $2$ | 按下按钮 $2$ | 停在按钮 $1$ | | $3$ | 移动到按钮 $3$ | 按下按钮 $1$ | | $4$ | 移动到按钮 $4$ | 移动到按钮 $2$ | | $5$ | 停在按钮 $4$ | 按下按钮 $2$ | | $6$ | 按下按钮 $4$ | 停在按钮 $2$ | 注意，Blue 必须等到 Orange 完全按完 O $2$ 之后，才能开始按 B $1$。

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 组测试数据。 每组测试数据为一行，首先是一个正整数 $N$，表示需要按下的按钮数量。接下来有 $N$ 个形如 "$R_i P_i$" 的项，其中 $R_i$ 表示机器人颜色（始终为 'O' 或 'B'），$P_i$ 表示按钮的位置。

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试编号（从 1 开始），$y$ 是机器人按顺序按下所有按钮所需的最少秒数。

**限制条件** - 对所有 $i$，$1 \leq P_i \leq 100$。 **小数据集（10 分，测试集 1 - 可见）** - $1 \leq T \leq 20$。 - $1 \leq N \leq 10$。 - 时间限制：3 秒。 **大数据集（10 分，测试集 2 - 隐藏）** - $1 \leq T \leq 100$。 - $1 \leq N \leq 100$。 - 时间限制：6 秒。 由 ChatGPT 4.1 翻译