1963:翻转01序列
文件提交:无需freopen
内存限制:128 MB
时间限制:1.000 S
评测方式:普通裁判
命题人:
提交:3
解决:2
题目描述
蒜头君最近迷上一个游戏--翻转 $01$ 序列。他有一个只包含 $0$ 和 $1$ 的序列,现在他想把这个序列变成另一个目标序列。每次,他可以选择序列的一个前缀并将它们全部翻转($0$ 变 $1$,$1$ 变 $0$)。蒜头君想知道最少需要多少次操作才能把初始序列变成目标序列。你能帮蒜头君解决这个问题吗?
输入
第一行输入一个整数 $n$,表示字符串长度。
第二行,输入一个字符串,表示初始序列。
第三行,输入一个字符串,表示目标序列,长度与初始序列相同。
$n \le 10^5$
输出
一个整数,表示最少需要的操作次数
样例输入-1 复制
4
1100
0011
样例输出-1 复制
1
样例输入-2 复制
4
1010
1001
样例输出-2 复制
2
提示
样例解释2:初始序列是 $1010$,目标序列是 $1001$。第 $1$ 次操作。翻转前缀 $1010$ 的前 $2$ 个字符,得到 $0110$。 第二次操作:翻转前缀 $0110$ 的前四个字符,得到 $1001$,最终变为目标序列,需要 $2$ 次操作。