題目大意：
輸入兩個括号序列 s,t（不一定合法），你需要構造一個盡可能短的合法括号序列使得s,t 都是這個序列的子序列（子序列意味着不用連續）
解題思路：
dp[i][j][k]
表示比對到
s
的第
i
個字元，比對到
t
的第
j
個字元，并且此時
(
的個數比
)
多
k
個的時候的最小合法序列長度，
k
的上限是200（s和t中最多200個
（
或者
)
）。
狀态轉移：
枚舉答案合法序列的每一位放置
(
或者
)
- 放置
(
s[i]=='(' -> ni=i+1
t[j]=='(' -> nj=j+1
dp[ni][nj][z+1]=dp[i][j][z]+1
- 放置
)
s[i]==')' -> ni=i+1
t[j]==')' -> nj=j+1
dp[ni][nj][z-1]=dp[i][j][z]+1
整個過程需要滿足
0<=z<=200
下界是因為
z<0
時左括号個數小于右括号個數将無法形成合法序列。每一個步轉移需要記錄父節點坐标和父節點通過什麼字元轉移到目前狀态，最終狀态為
dp[s.size()][t.size()][0]
，從這個狀态沿着父節點回退到
dp[0][0][0]
。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn=210;
const int inf=0x3f3f3f3f;
int dp[maxn][maxn][maxn];
struct node{int x,y,z;char c;}st[maxn][maxn][maxn];
string s,t;
int sz,tz;
int nx,ny,nz;
inline void bfs(){
sz=s.size(),tz=t.size();
memset(dp,0x3f,sizeof dp);
dp[0][0][0]=0;
queue<node> q;q.push(node{0,0,0});
while(!q.empty()){
node tp=q.front();q.pop();
//'('
nx=tp.x+(tp.x<sz&&s[tp.x]=='(');
ny=tp.y+(tp.y<tz&&t[tp.y]=='(');
nz=tp.z+1;
if(nz<=200&&dp[nx][ny][nz]==inf){
dp[nx][ny][nz]=dp[tp.x][tp.y][tp.z]+1;
q.push(node{nx,ny,nz});
st[nx][ny][nz]=node{tp.x,tp.y,tp.z,'('};
}
//)
nx=tp.x+(tp.x<sz&&s[tp.x]==')');
ny=tp.y+(tp.y<tz&&t[tp.y]==')');
nz=tp.z-1;
if(nz>=0&&dp[nx][ny][nz]==inf){
dp[nx][ny][nz]=dp[tp.x][tp.y][tp.z]+1;
q.push(node{nx,ny,nz});
st[nx][ny][nz]=node{tp.x,tp.y,tp.z,')'};
}
}
}
int main(){
cin>>s>>t;
bfs();
string res="";
int x=sz,y=tz,z=0;
int px,py,pz;
while(x||y||z){
res+=st[x][y][z].c;
px=st[x][y][z].x;
py=st[x][y][z].y;
pz=st[x][y][z].z;
x=px,y=py,z=pz;
}
sz=res.size();
for(int i=sz-1;i>=0;--i)cout<<res[i];
cout<<endl;
return 0;
}