[AGC030E] Less than 3

给定两个长度为 $n$ 的 `01` 串 $s,t$ , 串的连续段长度不超过 $2$ , 每次操作可以把 $s$ 的一个位置反转, 要求操作后连续段长度仍不超过 $2$ , 求使得 $s,t$ 相等的最少操作次数. $n\leqslant 5000$

[problemUrl]: https://atcoder.jp/contests/agc030/tasks/agc030_e 長さ $ N $ の文字列 $ s $ および $ t $ が与えられます。 $ s $ および $ t $ は `0` と `1` からなります。 また、$ s $ および $ t $ において、同一の文字が $ 3 $ 個以上連続する箇所はありません。 あなたは次の操作を繰り返し行い、$ s $ を書き換えていくことができます。 - 添字 $ i $ ($ 1\ \leq\ i\ \leq\ N $) を任意に選び、$ s $ の $ i $ 文字目を反転する (すなわち、`0` を `1` へ、`1` を `0` へ書き換える)。 ただし、操作後の $ s $ において、同一の文字が $ 3 $ 個以上連続する箇所があってはならない。 あなたの目標は $ s $ を $ t $ に一致させることです。 $ s $ を $ t $ に一致させるために必要な操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ s $ $ t $

$ s $ を $ t $ に一致させるために必要な操作回数の最小値を出力せよ。なお、有限回の操作で目的は必ず達成可能であることが証明できる。

4
0011
0101

4

1
0
0

0

8
00110011
10101010

10

### 制約 - $ 1\ \leq\ N\ \leq\ 5000 $ - $ s $ および $ t $ の長さは $ N $ である。 - $ s $ および $ t $ は `0` と `1` からなる。 - $ s $ および $ t $ において、同一の文字が $ 3 $ 個以上連続する箇所はない。 ### Sample Explanation 1 例えば、`0011` → `1011` → `1001` → `1101` → `0101` と操作を行えばよいです。