#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
const int N = 1e5 + 5;
int dp[N][5];
vector<int> vec{0, 1, 2};
signed main() {
int n;
string a, b;
cin >> n >> a >> b;
for(int i = 0; i < N; i++){
for(int j = 0; j < 5; j++) dp[i][j] = N;
}
dp[0][2] = 0;
for(int i = 1; i <= n; i++){
for(auto k:vec){
char p = k + '0';
if (i > 1 and k == 2) p = a[i - 2];
for(auto v:vec){
int cnt = dp[i - 1][k];
if(k != v and v != 2) cnt++;
char c = v + '0';
if(v == 2) c = a[i - 1];
if(c != b[i - 1] and (i == 1 or p == b[i - 2])) cnt++;
dp[i][k] = min(dp[i][k], cnt);
}
}
}
int ans = N;
for(int i = 0; i < 3; i++) ans = min(ans, dp[n][i]);
cout << ans << endl;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |