分数: 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