#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][4][4][4];
vector <pii> tmp;
void normal(vector <int> &v) {
tmp.clear();
REP(i, 3) tmp.pb({v[i], i});
sort(all(tmp));
int cnt = 1;
REP(i, 3) {
if (tmp[i].fi) v[tmp[i].sec] = cnt++;
}
}
int rek(int i, vector <int> v) {
normal(v);
int a = v[0], b = v[1], c = v[2];
if (i == n + 1) return 0;
if (dp[i][a][b][c] != -1) return dp[i][a][b][c];
int ret = inf;
int t = s[i];
if (b && (b < c || !c) && (b < a || !a)) t = 0;
if (c && (c < b || !b) && (c < a || !a)) t = 1;
if (a && (a < b || !b) && (a < c || !c)) {
if (b && (b < c || !c)) t = 1;
if (c && (c < b || !b)) t = 0;
if (!b && !c) t = s[i] ^ 1;
}
if (a && b && c && t != p[i]) return dp[i][a][b][c] = inf;
if (!a) ret = min(ret, rek(i, {3, b, c}) + 1);
if (!b) ret = min(ret, rek(i, {a, 3, c}) + 1);
if (!c) ret = min(ret, rek(i, {a, b, 3}) + 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;
//FOR(i, 1, n + 1) TRACE(i _ rek(i, {0, 0, 0}));
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
768 KB |
Output is correct |
| 4 |
Correct |
1 ms |
768 KB |
Output is correct |
| 5 |
Correct |
1 ms |
768 KB |
Output is correct |
| 6 |
Correct |
1 ms |
768 KB |
Output is correct |
| 7 |
Correct |
1 ms |
768 KB |
Output is correct |
| 8 |
Correct |
1 ms |
768 KB |
Output is correct |
| 9 |
Correct |
1 ms |
768 KB |
Output is correct |
| 10 |
Correct |
1 ms |
768 KB |
Output is correct |
| 11 |
Correct |
1 ms |
768 KB |
Output is correct |
| 12 |
Correct |
1 ms |
768 KB |
Output is correct |
| 13 |
Correct |
1 ms |
896 KB |
Output is correct |
| 14 |
Correct |
1 ms |
768 KB |
Output is correct |
| 15 |
Correct |
1 ms |
768 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
768 KB |
Output is correct |
| 4 |
Correct |
1 ms |
768 KB |
Output is correct |
| 5 |
Correct |
1 ms |
768 KB |
Output is correct |
| 6 |
Correct |
1 ms |
768 KB |
Output is correct |
| 7 |
Correct |
1 ms |
768 KB |
Output is correct |
| 8 |
Correct |
1 ms |
768 KB |
Output is correct |
| 9 |
Correct |
1 ms |
768 KB |
Output is correct |
| 10 |
Correct |
1 ms |
768 KB |
Output is correct |
| 11 |
Correct |
1 ms |
768 KB |
Output is correct |
| 12 |
Correct |
1 ms |
768 KB |
Output is correct |
| 13 |
Correct |
1 ms |
896 KB |
Output is correct |
| 14 |
Correct |
1 ms |
768 KB |
Output is correct |
| 15 |
Correct |
1 ms |
768 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
768 KB |
Output is correct |
| 4 |
Correct |
1 ms |
896 KB |
Output is correct |
| 5 |
Correct |
1 ms |
768 KB |
Output is correct |
| 6 |
Correct |
1 ms |
768 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
1 ms |
768 KB |
Output is correct |
| 3 |
Correct |
1 ms |
768 KB |
Output is correct |
| 4 |
Correct |
1 ms |
768 KB |
Output is correct |
| 5 |
Correct |
1 ms |
768 KB |
Output is correct |
| 6 |
Correct |
1 ms |
768 KB |
Output is correct |
| 7 |
Correct |
1 ms |
768 KB |
Output is correct |
| 8 |
Correct |
1 ms |
768 KB |
Output is correct |
| 9 |
Correct |
1 ms |
768 KB |
Output is correct |
| 10 |
Correct |
1 ms |
768 KB |
Output is correct |
| 11 |
Correct |
1 ms |
768 KB |
Output is correct |
| 12 |
Correct |
1 ms |
768 KB |
Output is correct |
| 13 |
Correct |
1 ms |
896 KB |
Output is correct |
| 14 |
Correct |
1 ms |
768 KB |
Output is correct |
| 15 |
Correct |
1 ms |
768 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
