Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- #define pb push_back
- #define ff first
- #define ss second
- #define oo 1000000000
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- const int mx=5005;
- int dp[mx][mx][2];
- int main(){
- ios::sync_with_stdio(false); cin.tie(0);
- int n; cin >> n;
- vector<int> a(n+1);
- for(int i=1;i<=n;++i){
- cin >> a[i];
- }
- int m; cin >> m;
- vector<int> b(m+1);
- for(int i=1;i<=m;++i){
- cin >> b[i];
- }
- memset(dp,127,sizeof(dp));
- dp[0][0][0]=dp[0][0][1]=0;
- for(int i=1;i<=n;++i){
- dp[i][0][0]=dp[i-1][0][0]+1;
- if(a[i]!=dp[i][0][0]%2) dp[i][0][0]++;
- }
- for(int i=1;i<=m;++i){
- dp[0][i][1]=dp[0][i-1][1]+1;
- if(b[i]!=dp[0][i][1]%2) dp[0][i][1]++;
- }
- for(int i=1;i<=n;++i){
- for(int j=1;j<=m;++j){
- dp[i][j][0]=min({dp[i][j][0],dp[i-1][j][0]+1+(a[i]==a[i-1]),dp[i-1][j][1]+1+(a[i]==b[j])});
- dp[i][j][1]=min({dp[i][j][1],dp[i][j-1][1]+1+(b[j]==b[j-1]),dp[i][j-1][0]+1+(b[j]==a[i])});
- }
- }
- cout << min(dp[n][m][0],dp[n][m][1]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement