题目描述

给定两个长度为 $N$ 的字符串 $s$ 和 $t$，它们只包含字符 0 和 1。此外，在 $s$ 和 $t$ 中，同一个字符不会连续出现 $3$ 次或以上。

你可以重复进行如下操作来修改 $s$：

• 任意选择一个下标 $i$（$1 \leq i \leq N$），将 $s$ 的第 $i$ 个字符反转（即将 0 变为 1，或将 1 变为 0）。但操作后，$s$ 中不能出现同一字符连续 $3$ 次或以上的情况。

你的目标是将 $s$ 变为 $t$。请你求出将 $s$ 变为 $t$ 所需的最小操作次数。

输入格式

输入以如下格式从标准输入读入：

$N$ $s$ $t$

输出格式

输出将 $s$ 变为 $t$ 所需的最小操作次数。可以证明一定存在有限次操作使目标达成。

样例 1

输入

4
0011
0101

输出

4

样例 2

输入

1
0
0

输出

0

样例 3

输入

8
00110011
10101010

输出

10

说明/提示

限制条件

• $1 \leq N \leq 5000$
• $s$ 和 $t$ 的长度均为 $N$。
• $s$ 和 $t$ 只包含字符 0 和 1。
• $s$ 和 $t$ 中不会出现同一字符连续 $3$ 次或以上的情况。

样例解释 1

例如，可以按如下顺序操作：0011 → 1011 → 1001 → 1101 → 0101。

由 ChatGPT 4.1 翻译