이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int dp[1000005], min1[1000005], min2[1000005], num1[1000005], num2[1000005], ind[1000005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
string s, t;
cin >> n >> s >> t;
s.insert(s.begin(), 0);
t.insert(t.begin(), 0);
s.insert(s.end(), 0);
t.insert(t.end(), 0);
for (int i=1; i<=n; i++)
{
num1[i]=(t[i]==t[i+1]?num1[i-1]:num1[i-1]+1);
num2[i]=(t[i]==t[i-1]?num2[i-1]:num2[i-1]+1);
ind[i]=(s[i]==t[i]?i:ind[i-1]);
if (num2[i]&1)
dp[i]=min1[i-1]+num2[i]/2+1;
else
dp[i]=min2[i-1]+num2[i]/2+1;
dp[i]=min(dp[i], dp[ind[i]]+1);
if (s[i]==t[i])
dp[i]=min(dp[i], dp[i-1]);
min1[i]=min(min1[i-1], dp[i]-num1[i]/2);
min2[i]=min(min2[i-1], dp[i]-(num1[i]+1)/2);
}
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... |