2929 - 二进制改造

题目描述

A 利用 C++ 程序,将整数 XY 转换成了两个长度均为 N 的二进制字符串 S_1S_2

现在他要对 S_2 进行改造,目标是将 S_2 改造为和 S_1 一样的字符串。

改造的方法是:每次小 A 可以将 S_2 中任意一段连续的子串中的 01 取反。也就是说,小 A 可以任意找一个连续的区间 [L,R]1 \le L \le R \le N),并将这个区间中的 0 取反为 11 取反为 0

请编程计算出,小 A 最少要改造多少次,才能实现改造目标?

输入

1 行读入整数 N,代表两个二进制字符串的长度。

2 行和第 3 行分别读入一个长度为 N 的仅含 01 的二进制字符串。

输出

输出最少的改造次数。

样例

输入

8
01110110
11000110

输出

2

输入

10
0100110101
0011101111

输出

3
说明

样例 1 解释

1 次改造:将 S_2 中的第 1 个字符 0 取反为 1,得到:01000110

1 次改造:将 S_2 中的位于区间 [3,4] 中的 01 取反,得到:01110110

数据范围

对于 100\% 的数据,满足 1 \le N \le 1000

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题