#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
return a.size();
}
void solve(){
int n;
#ifdef LOCAL
cin >> n;
#endif
string a, b; cin >> a >> b;
n = a.size();
for(int i = 0; i < n; i ++){
a[i] = (a[i] == b[i] ? '0' : '1');
}
a = "$" + a;
b = "$" + b;
//cout << a << '\n' << b << '\n';
vector<int> dp(n + 1);
for(int i = 1; i <= n; i ++){
int one = b[i] == '1';
int zer = b[i] == '0';
int xr = a[i] == '1';
dp[i] = min({dp[i - 1] + xr, dp[i - 1] + one + 1, dp[i - 1] + zer + 1});
for(int j = i - 1; j > 0; j --){
if(b[j] != b[j + 1]){
if(b[j] == '0') zer ++;
else one ++;
}
if(a[j] == '1' && a[j + 1] == '0'){
xr ++;
}
dp[i] = min({dp[i], dp[j - 1] + xr, dp[j - 1] + one + 1, dp[j - 1] + zer + 1});
}
assert(dp[i] >= dp[i - 1]);
//cout << i << ' ' << dp[i] << endl;
}
cout << dp[n];
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int testcases = 1;
#ifdef Tests
cin >> testcases;
#endif
while(testcases --){
solve();
if(testcases) cout << '\n';
#ifdef LOCAL
else
cout << '\n';
cout << "________________________" << endl;
#endif
}
#ifdef LOCAL
cout << "done" << endl;
#endif
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |