得分 : $1400$ 分

问题陈述

给定两个字符串 $s$ 和 $t$，它们的长度均为 $N$。
$s$ 和 $t$ 由 0 和 1 组成。此外，在这些字符串中，同一个字符不会连续出现三次或更多次。

你可以通过重复执行以下操作来修改 $s$：

• 自由选择一个索引 $i$ ($1 \leq i \leq N$)，并反转 $s$ 中的第 $i$ 个字符（即将 0 替换为 1，将 1 替换为 0），但操作后 $s$ 中同一个字符不得连续出现三次或更多次。

你的目标是使 $s$ 等于 $t$。找出所需的最小操作次数。

约束条件

• $1 \leq N \leq 5000$
• $s$ 和 $t$ 的长度均为 $N$。
• $s$ 和 $t$ 由 0 和 1 组成。
• 在 $s$ 和 $t$ 中，同一个字符不会连续出现三次或更多次。

输入

输入从标准输入以以下格式给出：

$N$

$s$

$t$

输出

找出将 $s$ 变为 $t$ 所需的最小操作次数。可以证明该目标始终在有限次数内实现。

4
0011
0101

4

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

1
0
0

0

8
00110011
10101010

10