Advertisement
HaciyevAlik

Untitled

Apr 2nd, 2023
428
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ld = long double;
  6. #define pb push_back
  7. #define ff first
  8. #define ss second
  9. #define oo 1000000000
  10.  
  11. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  12. const int mx=5005;
  13. int dp[mx][mx][2];
  14. int main(){
  15.     ios::sync_with_stdio(false); cin.tie(0);
  16.     int n; cin >> n;
  17.     vector<int> a(n+1);
  18.     for(int i=1;i<=n;++i){
  19.         cin >> a[i];
  20.     }
  21.     int m; cin >> m;
  22.     vector<int> b(m+1);
  23.     for(int i=1;i<=m;++i){
  24.         cin >> b[i];
  25.     }
  26.     memset(dp,127,sizeof(dp));
  27.     dp[0][0][0]=dp[0][0][1]=0;
  28.     for(int i=1;i<=n;++i){
  29.         dp[i][0][0]=dp[i-1][0][0]+1;
  30.         if(a[i]!=dp[i][0][0]%2) dp[i][0][0]++;
  31.     }
  32.     for(int i=1;i<=m;++i){
  33.         dp[0][i][1]=dp[0][i-1][1]+1;
  34.         if(b[i]!=dp[0][i][1]%2) dp[0][i][1]++;
  35.     }
  36.     for(int i=1;i<=n;++i){
  37.         for(int j=1;j<=m;++j){
  38.             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])});
  39.             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])});
  40.         }
  41.     }
  42.     cout << min(dp[n][m][0],dp[n][m][1]);
  43.     return 0;
  44. }
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement