#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n;
string a, b;
int dp[MAXN];
int nula (int lo, int hi) {
int res = 0;
for (int i = lo + 1; i <= hi; i++) {
if (b[i] == '1' && b[i - 1] == '0') res++;
}
if (b[hi] == '0') res++;
return res;
}
int jen (int lo, int hi) {
int res = 0;
for (int i = lo + 1; i <= hi; i++) {
if (b[i] == '0' && b[i - 1] == '1') res++;
}
if (b[hi] == '1') res++;
return res;
}
int raz (int lo, int hi) {
int res = 0;
for (int i = lo + 1; i <= hi; i++) {
if (a[i] == b[i] && a[i - 1] != b[i - 1]) res++;
}
if (a[hi] != b[hi]) res++;
return res;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b;
if (n > 18) return 0;
for (int i = 0; i < n; i++) {
dp[i] = 1e9;
for (int j = i; j >= 0; j--) {
int ost = (j == 0 ? 0 : dp[j - 1]);
dp[i] = min(dp[i], ost + raz(j, i));
dp[i] = min(dp[i], ost + 1 + jen(j, i));
dp[i] = min(dp[i], ost + 1 + nula(j, i));
}
}
cout << dp[n - 1];
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
4508 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
