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