← 返回题目列表

AtCoder · agc030_e

E. 小于 3

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

分数: 1400 点

问题陈述

给你字符串 s 和 t,长度均为 N. s 和 t 包括 0 和 1。此外,在这些字符串中,同一字符绝不会连续出现三次或更多次。

您可以修改 s 通过重复执行以下操作:

  • 选择一个索引 i (1 \leq i \leq N)自由并反转 i- 第一个字符 s (即替换 0 与 1,和 1 与 0),条件是同一字符不会连续出现 3 次或以上 s 操作后。

你的目标是 s 等于 t。 求出所需的最少操作次数。

约束

  • 1 \leq N \leq 5000
  • 的长度 s 和 t 都是 N.
  • s 和 t 包括 0 和 1.
  • In s 和 t,同一字符不会连续出现 3 次或更多次。

输入

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

N
s
t

输出

找出完成该操作所需的最少操作数 s 等于 t。可以证明,在有限次数的操作中,目标总是可以实现的。


示例输入 1

4
0011
0101

示例输出 1

4

一种可能的解决方案是 0011 → 1011 → 1001 → 1101 → 0101.


示例输入 2

1
0
0

示例输出 2

0

示例输入 3

8
00110011
10101010

示例输出 3

10