题意

给出两个括号序列 \(S\) 和 \(T\)，让你构造一个最短的合法括号序列使 \(S\) 和 \(T\) 是它的子序列。

分析

设 \(dp[i][j][k]\) 为这个最短的合法括号序列的前缀包含 \(S\) 的前 \(i\) 个字符，T的前 \(j\) 个字符且左括号的数量大于右括号的数量为 \(k\)时的长度。

• 如果我们要添加一个左括号

  \(dp[nexi][nexj][k+1]=min(dp[i][j][k]+1,dp[nexi][nexj][k+1])\)

  \(nexi\) 为添加一个左括号后能匹配到的下一个 \(i\)，\(nexj\) 为添加一个左括号能匹配到的下一个 \(j\)

• 如果我们要添加一个右括号

  \(dp[nexi][nexj][k-1]=min(dp[i][j][k]+1,dp[nexi][nexj][k-1])\)

  \(nexi\) 为添加一个右括号后能匹配到的下一个 \(i\)，\(nexj\) 为添加一个右括号能匹配到的下一个 \(j\)

\(dp\) 过程中用一个数组记录下转移的前驱就可以倒推还原这个括号序列。

Code

#include<bits/stdc++.h>

#define fi first

#define se second

#define lson l,mid,p<<1

#define rson mid+1,r,p<<1|1

#define pb push_back

#define ll long long

using namespace std;

const int inf=1e9;

const int mod=1e9+7;

const int maxn=2e2+10;

char s[maxn],t[maxn];

int n,m;

int dp[maxn][maxn][2*maxn];

struct ppo{

	int x,y,k;

	char c;

}pre[maxn][maxn][2*maxn];

int main(){

	//ios::sync_with_stdio(false);

	//freopen("in","r",stdin);

	scanf("%s%s",s,t);

	n=strlen(s);m=strlen(t);

	for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<2*maxn;k++) dp[i][j][k]=inf;

	dp[0][0][0]=0;

	for(int i=0;i<=n;i++){

		for(int j=0;j<=m;j++){

			for(int k=0;k<2*maxn;k++){

				if(dp[i][j][k]==inf) continue;

				int x=i+(i<n&&s[i]=='(');

				int y=j+(j<m&&t[j]=='(');

				if(k+1<2*maxn&&dp[i][j][k]+1<dp[x][y][k+1]){

					dp[x][y][k+1]=dp[i][j][k]+1;

					pre[x][y][k+1]=ppo{i,j,k,'('};

				}

				x=i+(i<n&&s[i]==')');

				y=j+(j<m&&t[j]==')');

				if(k>0&&dp[i][j][k]+1<dp[x][y][k-1]){

					dp[x][y][k-1]=dp[i][j][k]+1;

					pre[x][y][k-1]=ppo{i,j,k,')'};

				}

			}

		}

	}

	string str;

	int x=n,y=m,k=0,p=0;

    for(int i=0;i<2*maxn;i++){

        if(dp[n][m][p]+p>dp[n][m][i]+i) p=i;

    }

    for(int i=0;i<p;i++) str.pb(')');

    k=p;

	for(int i=0;i<dp[n][m][p];i++){

		ppo p=pre[x][y][k];

		str.pb(p.c);

		x=p.x;y=p.y;k=p.k;

	}

	reverse(str.begin(), str.end());

	cout<<str<<endl;

	return 0;

}