Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <cstdio>
- #include <iomanip>
- #include <fstream>
- #include <cassert>
- #include <cstring>
- #include <unordered_set>
- #include <unordered_map>
- #include <numeric>
- #include <ctime>
- #include <bitset>
- #include <complex>
- #include <random>
- using namespace std;
- const int N = 203;
- const int INF = 1e6 + 239;
- int dp[N][N][2 * N];
- tuple<int, int, int> wr[N][N][2 * N];
- string s, t;
- int n, m;
- void rlx(int i, int j, char c, int &ni, int &nj) {
- ni = i;
- nj = j;
- if (i < n && c == s[i]) {
- ni++;
- }
- if (j < m && c == t[j]) {
- nj++;
- }
- }
- void run(int i, int j, int bal) {
- int ni, nj;
- rlx(i, j, '(', ni, nj);
- if (bal + 1 < 2 * N) {
- if (dp[ni][nj][bal + 1] > dp[i][j][bal] + 1) {
- dp[ni][nj][bal + 1] = dp[i][j][bal] + 1;
- wr[ni][nj][bal + 1] = make_tuple(i, j, bal);
- }
- }
- rlx(i, j, ')', ni, nj);
- if (bal > 0) {
- if (dp[ni][nj][bal - 1] > dp[i][j][bal] + 1) {
- dp[ni][nj][bal - 1] = dp[i][j][bal] + 1;
- wr[ni][nj][bal - 1] = make_tuple(i, j, bal);
- }
- }
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cin >> s >> t;
- n = (int)s.size();
- m = (int)t.size();
- for (int i = 0; i <= n; i++) {
- for (int j = 0; j <= m; j++) {
- for (int bal = 0; bal < 2 * N; bal++) {
- dp[i][j][bal] = INF;
- wr[i][j][bal] = make_tuple(-1, -1, -1);
- }
- }
- }
- dp[0][0][0] = 0;
- for (int i = 0; i <= n; i++) {
- for (int j = 0; j <= m; j++) {
- for (int bal = 0; bal < 2 * N; bal++) {
- run(i, j, bal);
- }
- }
- }
- for (int i = 0; i <= n; i++) {
- for (int j = 0; j <= m; j++) {
- for (int bal = 0; bal < 2 * N; bal++) {
- run(i, j, bal);
- }
- }
- }
- int cb = 0;
- for (int b = 0; b < 2 * N; b++) {
- if (dp[n][m][b] + b < dp[n][m][cb] + cb) {
- cb = b;
- }
- }
- // cout << dp[n][m][cb] + cb << endl;
- int i = n;
- int j = m;
- int bal = cb;
- string out(cb, ')');
- while ((int)out.size() < dp[n][m][cb] + cb) {
- int ni, nj, nbal;
- tie(ni, nj, nbal) = wr[i][j][bal];
- if (nbal + 1 == bal) {
- out.push_back('(');
- } else {
- out.push_back(')');
- }
- i = ni;
- j = nj;
- bal = nbal;
- }
- reverse(out.begin(), out.end());
- cout << out << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement