This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define pb push_back
#define X first
#define Y second
#define debug(x) cerr << #x << " : " << x << endl;
#define all(x) x.begin() , x.end()
using namespace std;
typedef pair<int,int> pll;
typedef long long ll;
constexpr int N = 2e3+10;
int dp[N],a[N][3],pd[N][N][2];
int main(){
ios_base :: sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
string s,t;
cin >> s >> t;
s = '#'+s;
t = '#'+t;
rep(i,1,n+1){
if (t[i] == '1') a[i][1] = 1+a[i-1][1];
else a[i][0] = 1+a[i-1][0];
}
repr(l,n,1){
rep(r,l,n+1){
if (t[r] == '1'){
pd[l][r][1] = pd[l][r-1][1];
if (a[r][1] >= r-l+1){
pd[l][r][0] = 1;
continue;
}
pd[l][r][0] = pd[l][r-a[r][1]][0]+1;
}
else{
pd[l][r][0] = pd[l][r-1][0];
if (a[r][0] >= r-l+1){
pd[l][r][1] = 1;
continue;
}
pd[l][r][1] = pd[l][r-a[r][0]][1]+1;
}
}
}
rep(i,1,n+1){
if (s[i] == t[i]){
dp[i] = dp[i-1];
continue;
}
dp[i] = 1+dp[i-1];
bool fl = 1;
repr(j,i-1,1){
fl &= (s[j] != t[j]);
dp[i] = min(dp[i],dp[j-1]+min(pd[j][i][0],pd[j][i][1])+1);
if (fl) dp[i] = min(dp[i],dp[j-1]+1);
}
}
cout << dp[n];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |