Submission #124533

#TimeUsernameProblemLanguageResultExecution timeMemory
124533vexLamps (JOI19_lamps)C++14
4 / 100
30 ms20108 KiB
#include <bits/stdc++.h> #define maxn 1000005 #define INF 10020000 using namespace std; int n; string a,b; int dp[maxn][2][2]; int minn(int x) { return min(min(dp[x][0][0],dp[x][0][1]), min(dp[x][1][0],dp[x][1][1])); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n; cin>>a; cin>>b; if(a[0]==b[0]) { dp[0][0][0]=0; dp[0][0][1]=INF; dp[0][1][0]=1; dp[0][1][1]=2; } else { dp[0][0][0]=INF; dp[0][0][1]=1; dp[0][1][0]=1; dp[0][1][1]=2; } for(int i=1;i<n;i++) { if(a[i]==b[i]) { dp[i][0][0]=minn(i-1); dp[i][0][1]=INF; dp[i][1][0]=minn(i-1)+1; if(b[i-1]==b[i])dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][0]); else dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][1]); dp[i][1][1]=minn(i-1)+2; if(b[i]==b[i-1])dp[i][1][1]=min(dp[i][1][1],dp[i-1][1][1]); if(b[i-1]+b[i]==1)dp[i][1][1]=min(dp[i][1][1],dp[i-1][1][0]+1); dp[i][1][1]=min( min(dp[i-1][0][1],dp[i-1][1][1])+1, dp[i][1][1]); } else { dp[i][0][0]=INF; dp[i][0][1]=min( min(dp[i-1][0][1],dp[i-1][1][1]), min(dp[i-1][0][0],dp[i-1][1][0])+1 ); dp[i][1][0]=minn(i-1)+1; if(b[i-1]==b[i])dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][0]); else dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][1]); dp[i][1][1]=minn(i-1)+2; if(b[i]==b[i-1])dp[i][1][1]=min(dp[i][1][1],dp[i-1][1][1]); if(b[i-1]+b[i]==1)dp[i][1][1]=min(dp[i][1][1],dp[i-1][1][0]+1); dp[i][1][1]=min( min(dp[i-1][0][1],dp[i-1][1][1])+1, dp[i][1][1]); } } /*for(int i=0;i<n;i++) { cout<<i<<": "<<dp[i][0][0]<<" "<<dp[i][0][1]<<" "<<dp[i][1][0]<<" "<<dp[i][1][1]<<endl; }*/ cout<<minn(n-1)<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...