P14347 [JOISC 2019] 灯 / Lamps

一条长走廊上排列着 $N$ 盏灯，灯的编号从 $1$ 到 $N$。每盏灯的状态为关闭或开启。存在一种特殊机制可改变灯的状态。在一次操作中，我们可以执行以下三种操作之一： - 选择满足 $1 \le p \le q \le N$ 的整数 $p$ 和 $q$，并将灯 $p, p+1, \dots, q$ 全部关闭。 - 选择满足 $1 \le p \le q \le N$ 的整数 $p$ 和 $q$，并将灯 $p, p+1, \dots, q$ 全部开启。 - 选择满足 $1 \le p \le q \le N$ 的整数 $p$ 和 $q$，并将灯 $p, p+1, \dots, q$ 的状态全部翻转（关闭变开启，开启变关闭）。 灯的当前状态由长度为 $N$ 的字符串 $A$ 表示。若灯 $i$（$1 \le i \le N$）处于关闭状态，则字符串 $A$ 的第 $i$ 个字符为 $0$；若处于开启状态，则为 $1$。我们希望将灯的状态变为由长度为 $N$ 的字符串 $B$ 所表示的目标状态，且操作次数尽可能少。若希望灯 $i$（$1 \le i \le N$）处于关闭状态，则字符串 $B$ 的第 $i$ 个字符为 $0$；若希望其处于开启状态，则为 $1$。 请编写一个程序，输入灯的数量、当前状态和目标状态，计算并输出达到目标状态所需的最少操作次数。

从标准输入读取以下数据： $N$ $A$ $B$

向标准输出写入一行。该行应包含达到目标状态所需的最少操作次数。

### 数据范围 - $1 \le N \le 1000000$。 - $A$ 和 $B$ 均为长度为 $N$ 的字符串。 - 字符串 $A$ 和 $B$ 中的每个字符均为 $0$ 或 $1$。 ### 子任务 1. （6 分）$N \le 18$。 2. （41 分）$N \le 2000$。 3. （4 分）字符串 $A$ 中的每个字符均为 $0$。 4. （49 分）无额外约束。 翻译由 Qwen3-235B 完成