# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # pragma GCC optimize "-O3"
# define int long long
using namespace std;
const int N = 1e6 + 7;
const int INF = 1e9 + 7;
int dp[N], DP[N][4], dp0[N][4], dp3[N][4];
string s, t;
int Min( int i, int j ) {
int mn = dp0[i - 1][j], mn2 = INF, x = (j != 3);
for ( int k = 0; k < 4; k++ ) {
if ( k != j ) {
mn2 = min( mn2, dp0[i - 1][k] + x );
}
}
return min( mn, mn2 );
}
int Min1( int i, int j ) {
int mn = dp3[i - 1][j], mn2 = INF, x = (j != 3);
for ( int k = 0; k < 4; k++ ) {
if ( k != j ) {
mn2 = min( mn2, dp3[i - 1][k] + x );
}
}
return min( mn, mn2 );
}
void change( int j ) {
for ( int i = 0; i < 4; i++ ) {
if ( !dp0[j][i] ) {
dp0[j][i] = INF;
}
}
}
void change1( int j ) {
for ( int i = 0; i < 4; i++ ) {
if ( !dp3[j][i] ) {
dp3[j][i] = INF;
}
}
}
void output( int i ) {
cout << dp0[i][0] << " " << dp0[i][1] << " " << dp0[i][2] << " " << dp0[i][3] << '\n';
}
void calc0( char x, int i ) {
if ( x == '1' ) {
if ( t[i] == '1' ) {
dp0[i][1] = Min( i, 1 );
dp0[i][3] = Min( i, 3 );
}
else {
dp0[i][0] = Min( i, 0 );
dp0[i][2] = Min( i, 2 );
}
}
else {
if ( t[i] == '1' ) {
dp0[i][1] = Min( i, 1 );
dp0[i][2] = Min( i, 2 );
}
else {
dp0[i][0] = Min( i, 0 );
dp0[i][3] = Min( i, 3 );
}
}
}
void calc1( char x, int i ) {
if ( x == '1' ) {
if ( t[i] == '1' ) {
dp3[i][1] = Min1( i, 1 );
dp3[i][3] = Min1( i, 3 );
}
else {
dp3[i][0] = Min1( i, 0 );
dp3[i][2] = Min1( i, 2 );
}
}
else {
if ( t[i] == '1' ) {
dp3[i][1] = Min1( i, 1 );
dp3[i][2] = Min1( i, 2 );
}
else {
dp3[i][0] = Min1( i, 0 );
dp3[i][3] = Min1( i, 3 );
}
}
}
int32_t main() {
speed;
int n;
cin >> n;
cin >> s >> t;
if ( s[0] == '1' ) {
if ( t[0] == '0' ) {
dp0[0][0] = 1;
dp0[0][2] = 1;
}
if ( t[0] == '1' ) {
dp0[0][1] = 1;
dp0[0][3] = 0;
}
}
else {
if ( t[0] == '0' ) {
dp0[0][0] = 1;
dp0[0][3] = 0;
}
if ( t[0] == '1' ) {
dp0[0][1] = 1;
dp0[0][2] = 1;
}
}
change( 0 );
DP[0][0] = min( { dp0[0][0], dp0[0][1], dp0[0][2], dp0[0][3] } );
if ( s[0] == '0' ) {
if ( t[0] == '0' ) {
dp3[0][0] = 1;
dp3[0][2] = 1;
}
if ( t[0] == '1' ) {
dp3[0][1] = 1;
dp3[0][3] = 0;
}
}
else {
if ( t[0] == '0' ) {
dp3[0][0] = 1;
dp3[0][3] = 0;
}
if ( t[0] == '1' ) {
dp3[0][1] = 1;
dp3[0][2] = 1;
}
}
change1( 0 );
DP[0][3] = min( { dp3[0][0], dp3[0][1], dp3[0][2], dp3[0][3] } );
// output(0);
for ( int i = 1; i < n; i++ ) {
if ( s[i] == '1' ) {
if ( t[i] == '1' ) {
dp0[i][1] = Min( i, 1 );
dp0[i][3] = Min( i, 3 );
}
else {
dp0[i][0] = Min( i, 0 );
dp0[i][2] = Min( i, 2 );
}
}
else {
if ( t[i] == '1' ) {
dp0[i][1] = Min( i, 1 );
dp0[i][2] = Min( i, 2 );
}
else {
dp0[i][0] = Min( i, 0 );
dp0[i][3] = Min( i, 3 );
}
}
calc0( s[i], i );
change(i);
DP[i][0] = min( { dp0[i][0], dp0[i][1], dp0[i][2], dp0[i][3] } );
char x = '0' + ( 1 - (s[i] - '0') );
calc1( x, i );
change1(i);
DP[i][3] = min( { dp3[i][0], dp3[i][1], dp3[i][2], dp3[i][3] } );
// output(i);
}
int one = 0, zero = 0, cnt0 = 0, cnt1 = 0;
for ( int i = 0; i < n; i++ ) {
dp[i] = INF;
if ( t[i] == '0' ) {
if ( !zero ) {
zero = 1;
cnt0++;
}
one = 0;
}
else {
if ( !one ) {
one = 1;
cnt1++;
}
zero = 0;
}
DP[i][1] = cnt0;
DP[i][2] = cnt1;
// cout << i << " " << DP[i][0] << ' ' << DP[i][1] << ' ' << DP[i][2] << " " << DP[i][3] << "\n";
}
for ( int i = 0; i < n; i++ ) {
for ( int j = i; j >= 0; j-- ) {
int cnt = 0;
if ( j ) {
cnt += dp[j - 1];
for ( int k = 1; k < 4; k++ ) {
dp[i] = min( dp[i], DP[i][k] - DP[j - 1][k] + cnt + 1 );
}
}
}
dp[i] = min( { dp[i], DP[i][0], DP[i][1] + 1, DP[i][2] + 1, DP[i][3] + 1 } );
// cout << i << " " << dp[i] << "\n";
}
cout << dp[n - 1];
}
// 1. DP[i][0] = minimum number of moves without wrong range queries from 1->i : dp0; Done
// 2. DP[i][1] = number of 1 segments ; Done
// 3. DP[i][2] = number of 0 segments ; Done
// 4. DP[i][3] = same as [0] but with 1 - s[i] : dp3; Done
// 5. dp[i] = minimum number of moves to solve till i
// 6. change dp[i] with minimum dp[j - 1] - DP[j - 1][k]; j < i, k < 4
// 7. store the 6'th point in a set to find the minimum
// 8. return dp[n - 1];
// 9. 0% belief in this code
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
