大样例下载

题目描述

有一个长度为 N 的 01 字符串 S。

你希望通过若干次操作将字符串 S 变成字符串 T。

有以下三种类型的操作供你选择：

• 子串清零：选择某一个子串，将其全部变成字符 0

• 子串归一：选择某一个子串，将其全部变成字符 1

• 子串取反：选择某一个子串，将其中的 0 全部变成 1，其中的 1 全部变成 0

你可以操作任意次。每次操作，你可以选择任意一个子串进行以上某种类型的操作。

问：你想将 S 变成 T 最少需要多少次操作？

输入格式

第 1 行：一个整数 N

第 2 行：一个长度为 N 的 01 字符串 S

第 3 行：一个长度为 N 的 01 字符串 T

输出格式

一个整数，表示答案。

样例输入

10
0001011011
0110110001

样例输出

2

样例解释

操作方案不唯一，以下是一种可能方案：

0001011011 ---划线子串取反---> 0110111011 ---划线子串清零---> 0110110001

数据范围

100% 的数据：$1 ≤ N ≤ 10^6$。

本题目采用子任务捆绑测试，只有通过子任务下所有数据点测试，才能得到相应子任务的分数。

子任务1（6分）：$1 ≤ N ≤ 18$

子任务2（41分）：$1 ≤ N ≤ 2000$

子任务3（4分）：$S 全部字符均为$ 0

子任务4（49分）：$1 ≤ N ≤ 10^6$