#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;
#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<
#define fi first
#define sec second
#define mp make_pair
#define pb push_back
const int MAXN = 2010;
const int inf = 2000000;
int n;
char s[MAXN], p[MAXN];
int dp[MAXN][2][2][2];
int rek(int i, int a, int b, int c) {
if (b && c) return inf;
if (i == n + 1) return 0;
if (dp[i][a][b][c] != -1) return dp[i][a][b][c];
int ret = inf;
if (a && !b && !c && s[i] == p[i]) return dp[i][a][b][c] = inf;
if (b && p[i]) return dp[i][a][b][c] = inf;
if (c && !p[i]) return dp[i][a][b][c] = inf;
if (!a) ret = min(ret, rek(i, 1, b, c) + 1);
if (!b) ret = min(ret, rek(i, a, 1, c) + 1);
if (!c) ret = min(ret, rek(i, a, b, 1) + 1);
int t = s[i] ^ a;
if (b) t = 0;
if (c) t = 1;
if (t == p[i]) {
ret = min(ret, rek(i + 1, a, b, c));
ret = min(ret, rek(i + 1, 0, b, c));
ret = min(ret, rek(i + 1, 0, 0, c));
ret = min(ret, rek(i + 1, 0, 0, 0));
ret = min(ret, rek(i + 1, a, 0, c));
ret = min(ret, rek(i + 1, a, b, 0));
ret = min(ret, rek(i + 1, a, 0, 0));
ret = min(ret, rek(i + 1, 0, b, 0));
}
return dp[i][a][b][c] = ret;
}
int main() {
cin >> n;
cin >> s >> p;
REP(i, n) {
s[i] -= '0';
p[i] -= '0';
}
for (int i = n; i > 0; i--) {
s[i] = s[i - 1];
p[i] = p[i - 1];
}
memset(dp, -1, sizeof dp);
cout << rek(1, 0, 0, 0) << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 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 |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 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 |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
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 |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
