Guest User

Untitled

a guest
Dec 12th, 2019
447
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <complex>
  20. #include <random>
  21.  
  22. using namespace std;
  23.  
  24. const int N = 203;
  25. const int INF = 1e6 + 239;
  26.  
  27. int dp[N][N][2 * N];
  28. tuple<int, int, int> wr[N][N][2 * N];
  29.  
  30. string s, t;
  31. int n, m;
  32.  
  33. void rlx(int i, int j, char c, int &ni, int &nj) {
  34.     ni = i;
  35.     nj = j;
  36.     if (i < n && c == s[i]) {
  37.         ni++;
  38.     }
  39.     if (j < m && c == t[j]) {
  40.         nj++;
  41.     }
  42. }
  43.  
  44. void run(int i, int j, int bal) {
  45.     int ni, nj;
  46.     rlx(i, j, '(', ni, nj);
  47.     if (bal + 1 < 2 * N) {
  48.         if (dp[ni][nj][bal + 1] > dp[i][j][bal] + 1) {
  49.             dp[ni][nj][bal + 1] = dp[i][j][bal] + 1;
  50.             wr[ni][nj][bal + 1] = make_tuple(i, j, bal);
  51.         }
  52.     }
  53.     rlx(i, j, ')', ni, nj);
  54.     if (bal > 0) {
  55.         if (dp[ni][nj][bal - 1] > dp[i][j][bal] + 1) {
  56.             dp[ni][nj][bal - 1] = dp[i][j][bal] + 1;
  57.             wr[ni][nj][bal - 1] = make_tuple(i, j, bal);
  58.         }
  59.     }
  60. }
  61.  
  62. signed main() {
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(0);
  65.  
  66.     cin >> s >> t;
  67.     n = (int)s.size();
  68.     m = (int)t.size();
  69.     for (int i = 0; i <= n; i++) {
  70.         for (int j = 0; j <= m; j++) {
  71.             for (int bal = 0; bal < 2 * N; bal++) {
  72.                 dp[i][j][bal] = INF;
  73.                 wr[i][j][bal] = make_tuple(-1, -1, -1);
  74.             }
  75.         }
  76.     }
  77.     dp[0][0][0] = 0;
  78.     for (int i = 0; i <= n; i++) {
  79.         for (int j = 0; j <= m; j++) {
  80.             for (int bal = 0; bal < 2 * N; bal++) {
  81.                 run(i, j, bal);
  82.             }
  83.         }
  84.     }
  85.     for (int i = 0; i <= n; i++) {
  86.         for (int j = 0; j <= m; j++) {
  87.             for (int bal = 0; bal < 2 * N; bal++) {
  88.                 run(i, j, bal);
  89.             }
  90.         }
  91.     }
  92.     int cb = 0;
  93.     for (int b = 0; b < 2 * N; b++) {
  94.         if (dp[n][m][b] + b < dp[n][m][cb] + cb) {
  95.             cb = b;
  96.         }
  97.     }
  98.     // cout << dp[n][m][cb] + cb << endl;
  99.     int i = n;
  100.     int j = m;
  101.     int bal = cb;
  102.     string out(cb, ')');
  103.     while ((int)out.size() < dp[n][m][cb] + cb) {
  104.         int ni, nj, nbal;
  105.         tie(ni, nj, nbal) = wr[i][j][bal];
  106.         if (nbal + 1 == bal) {
  107.             out.push_back('(');
  108.         } else {
  109.             out.push_back(')');
  110.         }
  111.         i = ni;
  112.         j = nj;
  113.         bal = nbal;
  114.     }  
  115.     reverse(out.begin(), out.end());
  116.     cout << out << endl;
  117. }
RAW Paste Data