← 返回题目列表

AtCoder · arc109_f

F. 1D 王国建设者

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

分数: 900 点

问题陈述

Snuke 正在玩一个由无数个排成一排的方块组成的棋盘。 每个方格都有一个指定的整数;对于每个整数 i,方形 i 和广场 i+1 相邻。 此外,每个方块都被漆成白色或黑色。

一个字符串 s 长度 n 组成 w 和 b 代表这块棋盘的方格颜色,如下:

  • 对于每个 i = 1, 2, \dots, n,方形 i 为白色,如果 i- 第一个字符 s is w,如果该字符是黑色 b;
  • 对于每个 i \leq 0,方形 i 为白色;
  • 对于每个 i > n,方形 i 是黑色的。

Snuke 有无限多个白色棋子和无限多个黑色棋子。他将把这些棋子放在棋盘上,如下所示:

  • (1) 选择一块自己喜欢的颜色。
  • (2) 在与已包含棋子的方格相邻的方格中,寻找与所选棋子颜色相同的方格。
    • (2a) 如果有这样的格子,选择其中一个,并将棋子放在上面;
    • (2b) 如果没有这样的方块,则选择一个与所选棋子颜色相同的方块并将棋子放在上面。

棋盘上最初没有棋子。

给你一个字符串 t 长度 n 组成 o 和 _。找出 Snuke 需要在棋盘上放置的最小棋子数量,以便每个方格上都有一个棋子 方块中的 i 方格之间 1,..,n 这样 i- 第一个字符 t is o。 可以保证 t 至少出现一次 o.

约束

  • 1 \leq n \leq 10^5
  • |s| = |t| = n
  • s 包括 w 和 b.
  • t 包括 o 和 _.
  • t 至少出现一次 o.

输入

输入由标准输入按以下格式给出:

n
s
t

输出

打印 Snuke 需要放在板上的最小件数。


样本输入 1

3
wbb
o_o

示例输出 1

2

让我们使用 W 代表一个需要在其上放置棋子的白色方块, B 代表一个需要在其上放置棋子的黑色方块, w 代表一个不需要棋子的白色方块,并且 b 代表一个不需要棋子的黑色方块。

我们有以下主板:

...wwwwwwWbBbbbbb...

如果我们按以下顺序放置碎片,两块就足够了:

...wwwwwwWbBbbbbb...
         2 1

请注意,如果我们先在白色方块上放置一个棋子,我们将需要三个或更多棋子:

...wwwwwwWbBbbbbb...
         123

示例输入 2

4
wwww
o__o

示例输出 2

3

如果我们按以下顺序放置碎片,则三块就足够了:

...wwwwwWwwWbbbbb...
        1  32

示例输入 3

9
bbwbwbwbb
_o_o_o_o_

示例输出 3

5

如果我们按以下顺序放置碎片,则五块就足够了:

...wwwwwbBwBwBwBbbbbbb...
        12 3 4 5

示例输入 4

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_

示例输出 4

11