← 返回题目列表

Codeforces · 748/C

C. 圣诞老人和机器人

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

圣诞老人有一个机器人,它生活在无限的网格上,可以沿着它的线移动。他还可以通过具有整数坐标的 m 个点 p1, p2, ..., pm 的序列,执行以下操作:用 p0 表示其初始位置。首先,机器人将沿着它们之间的最短路径之一从 p0 移动到 p1(请注意,由于机器人仅沿着网格线移动,因此可以有几条最短路径)。然后,在到达 p1 后,它将再次移动到 p2,选择最短路线之一,然后移动到 p3,依此类推,直到他按给定顺序访问了所有点。序列中的某些点可能会重合,在这种情况下,机器人将根据序列顺序多次访问该点。

当圣诞老人离开时,有人给了机器人一系列的分数。该序列现已丢失,但机器人保存了其单位运动的协议。请找出该序列的最小可能长度。

输入

输入的第一行包含唯一的正整数 n (1 ≤ n ≤ 2·105),它等于机器人行驶的单位段数。第二行包含运动协议,由 n 个字母组成,每个字母等于 L、R、U 或 D。第 k 个字母代表机器人行进第 k 个单位段的方向:L 表示它向左移动,R — 向右移动,U — 向顶部移动,D — 向底部移动。查看插图以获得更好的解释。

输出

唯一的输入行应包含序列的最小可能长度。

示例

输入 #1

4
RURD

输出 #1

2

输入 #2

6
RRULDD

输出 #2

2

输入 #3

26
RRRULURURUULULLLDLDDRDRDLD

输出 #3

7

输入#4

3
RLL

输出#4

2

输入 #5

4
LRLR

输出 #5

4

注意

前三个测试的插图如下。

最后一个示例说明序列中的每个点应按照其在序列中出现的次数进行计数。