#include <bits/stdc++.h>
using namespace std;
//#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl
typedef long long ll;
int n;
string s, t;
int dp[1000006][16];
void mini(int& a, int b){
a = min(a, b);
}
int g(int ma, int mb){
if (ma == mb) return 0;
if (ma == 0) return 0;
if (ma == 1) return (mb != 4 && mb != 5 && mb != 10 && mb != 11);
if (ma == 2) return (mb != 6 && mb != 7 && mb != 12 && mb != 13);
if (ma == 3) return (mb != 8 && mb != 9 && mb != 14 && mb != 15);
if (ma == 4){
if (mb == 11) return 0;
if (mb == 1 || mb == 5 || mb == 10) return 1;
return 2;
}
if (ma == 5){
if (mb == 10) return 0;
if (mb == 1 || mb == 4 || mb == 11) return 1;
return 2;
}
if (ma == 6){
if (mb == 13) return 0;
if (mb == 2 || mb == 7 || mb == 12) return 1;
return 2;
}
if (ma == 7){
if (mb == 12) return 0;
if (mb == 2 || mb == 6 || mb == 13) return 1;
return 2;
}
if (ma == 8){
if (mb == 14) return 0;
if (mb == 3 || mb == 9 || mb == 15) return 1;
return 2;
}
if (ma == 9) {
if (mb == 15) return 0;
if (mb == 3 || mb == 8 || mb == 14) return 1;
return 2;
}
if (ma == 10){
if (mb == 5) return 1;
if (mb == 1 || mb == 4 || mb == 11) return 2;
return 3;
}
if (ma == 11){
if (mb == 4) return 1;
if (mb == 1 || mb == 5 || mb == 10) return 2;
return 3;
}
if (ma == 12){
if (mb == 7) return 1;
if (mb == 2 || mb == 6 || mb == 13) return 2;
return 3;
}
if (ma == 13){
if (mb == 6) return 1;
if (mb == 2 || mb == 7 || mb == 12) return 2;
return 3;
}
if (ma == 14){
if (mb == 8) return 1;
if (mb == 3 || mb == 8 || mb == 9 || mb == 14 || mb == 15) return 2;
return 3;
}
if (ma == 15){
if (mb == 9) return 1;
if (mb == 3 || mb == 8 || mb == 9 || mb == 14 || mb == 15) return 2;
return 3;
}
assert(0);
}
int f(int ind, int mod){
if (ind == n) return g(mod, 0);
if (dp[ind][mod] != -1) return dp[ind][mod];
//cout << "f(" << ind << ", " << mod << ")" << endl;
int ans = 10000000;
if (s[ind] == '0' && t[ind] == '0'){
mini(ans, g(mod, 0) + f(ind+1, 0));
mini(ans, g(mod, 1) + f(ind+1, 1));
mini(ans, g(mod, 6) + f(ind+1, 6));
mini(ans, g(mod, 7) + f(ind+1, 7));
mini(ans, g(mod, 9) + f(ind+1, 9));
mini(ans, g(mod, 10) + f(ind+1, 10));
mini(ans, g(mod, 13) + f(ind+1, 13));
mini(ans, g(mod, 14) + f(ind+1, 14));
} else if (s[ind] == '1' && t[ind] == '0'){
mini(ans, g(mod, 1) + f(ind+1, 1));
mini(ans, g(mod, 3) + f(ind+1, 3));
mini(ans, g(mod, 6) + f(ind+1, 6));
mini(ans, g(mod, 7) + f(ind+1, 7));
mini(ans, g(mod, 9) + f(ind+1, 9));
mini(ans, g(mod, 10) + f(ind+1, 10));
mini(ans, g(mod, 13) + f(ind+1, 13));
mini(ans, g(mod, 14) + f(ind+1, 14));
} else if (s[ind] == '0' && t[ind] == '1'){
mini(ans, g(mod, 2) + f(ind+1, 2));
mini(ans, g(mod, 3) + f(ind+1, 3));
mini(ans, g(mod, 4) + f(ind+1, 4));
mini(ans, g(mod, 5) + f(ind+1, 5));
mini(ans, g(mod, 8) + f(ind+1, 8));
mini(ans, g(mod, 11) + f(ind+1, 11));
mini(ans, g(mod, 12) + f(ind+1, 12));
mini(ans, g(mod, 15) + f(ind+1, 15));
} else if (s[ind] == '1' && t[ind] == '1'){
mini(ans, g(mod, 0) + f(ind+1, 2));
mini(ans, g(mod, 2) + f(ind+1, 3));
mini(ans, g(mod, 4) + f(ind+1, 4));
mini(ans, g(mod, 5) + f(ind+1, 5));
mini(ans, g(mod, 8) + f(ind+1, 8));
mini(ans, g(mod, 11) + f(ind+1, 11));
mini(ans, g(mod, 12) + f(ind+1, 12));
mini(ans, g(mod, 15) + f(ind+1, 15));
} else assert(0);
return dp[ind][mod] = ans;
}
int main(){
cin >> n >> s >> t;
//cout << s << " " << t << endl;
//for (int i = 0; i < 16; i++) cout << bas(g(i, 1)) << endl;
for (int i = 0; i < n; i++) for (int j = 0; j < 16; j++) dp[i][j] = -1;
cout << f(0, 0) << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
777 ms |
145380 KB |
Output is correct |
| 8 |
Correct |
801 ms |
145404 KB |
Output is correct |
| 9 |
Correct |
807 ms |
145380 KB |
Output is correct |
| 10 |
Correct |
793 ms |
145580 KB |
Output is correct |
| 11 |
Correct |
805 ms |
145424 KB |
Output is correct |
| 12 |
Correct |
778 ms |
145440 KB |
Output is correct |
| 13 |
Correct |
774 ms |
145252 KB |
Output is correct |
| 14 |
Correct |
775 ms |
145356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
