/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1400 点
問題文
長さ 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 に一致させるために必要な操作回数の最小値を求めてください。
制約
- 1 \leq N \leq 5000
- s および t の長さは N である。
- s および t は
0と1からなる。 - s および t において、同一の文字が 3 個以上連続する箇所はない。
入力
入力は以下の形式で標準入力から与えられる。
N s t
出力
s を t に一致させるために必要な操作回数の最小値を出力せよ。なお、有限回の操作で目的は必ず達成可能であることが証明できる。
入力例 1
4 0011 0101
出力例 1
4
例えば、0011 → 1011 → 1001 → 1101 → 0101 と操作を行えばよいです。
入力例 2
1 0 0
出力例 2
0
入力例 3
8 00110011 10101010
出力例 3
10
Score : 1400 points
Problem Statement
You are given strings s and t, both of length N.
s and t consist of 0 and 1. Additionally, in these strings, the same character never occurs three or more times in a row.
You can modify s by repeatedly performing the following operation:
- Choose an index i (1 \leq i \leq N) freely and invert the i-th character in s (that is, replace
0with1, and1with0), under the condition that the same character would not occur three or more times in a row in s after the operation.
Your objective is to make s equal to t. Find the minimum number of operations required.
Constraints
- 1 \leq N \leq 5000
- The lengths of s and t are both N.
- s and t consists of
0and1. - In s and t, the same character never occurs three or more times in a row.
Input
Input is given from Standard Input in the following format:
N s t
Output
Find the minimum number of operations required to make s equal to t. It can be proved that the objective is always achievable in a finite number of operations.
Sample Input 1
4 0011 0101
Sample Output 1
4
One possible solution is 0011 → 1011 → 1001 → 1101 → 0101.
Sample Input 2
1 0 0
Sample Output 2
0
Sample Input 3
8 00110011 10101010
Sample Output 3
10