Codeforces #605 : Div3. F. Two Bracket Sequences

これは割と典型な問題かも。
https://codeforces.com/contest/1272/problem/F

問題

２つの括弧列S,Tが与えられる。
S,Tを(不連続でも良い)部分列として含むような正規の括弧列のうち、最短のものを構築せよ。

以下の状態を考え、順にDPで埋めて行こう。その際、直前どの状態から遷移したかも覚えておく。
dp(s,t,p) := S,Tのうちprefix s,t文字を部分列として含み、かつ開き括弧がp個先行しているような括弧列の最短の文字列長

dp(|S|,|T|,0)が求められたら、復元していけばよい。

string S,T;
int A,B;

int hoge[202][202][204];
vector<int> from[202][202][204];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	A=S.size();
	B=T.size();
	
	memset(hoge,0x11,sizeof(hoge));
	hoge[0][0][0]=0;
	FOR(x,A+1) FOR(y,B+1) {
		FOR(i,102) {
			// '('
			int nx=x;
			int ny=y;
			if(x<A && S[x]=='(') nx++;
			if(y<B && T[y]=='(') ny++;
			if(hoge[x][y][i]+1<hoge[nx][ny][i+1]) {
				hoge[nx][ny][i+1]=hoge[x][y][i]+1;
				from[nx][ny][i+1]={x,y,i,'('};
			}
			nx=x,ny=y;
			if(x<A && S[x]==')') nx++;
			if(y<B && T[y]==')') ny++;
			if(i && hoge[x][y][i]+1<hoge[nx][ny][i-1]) {
				hoge[nx][ny][i-1]=hoge[x][y][i]+1;
				from[nx][ny][i-1]={x,y,i,')'};
			}
		}
		for(i=100;i>=0;i--) {
			// '('
			int nx=x;
			int ny=y;
			if(x<A && S[x]=='(') nx++;
			if(y<B && T[y]=='(') ny++;
			if(hoge[x][y][i]+1<hoge[nx][ny][i+1]) {
				hoge[nx][ny][i+1]=hoge[x][y][i]+1;
				from[nx][ny][i+1]={x,y,i,'('};
			}
			nx=x,ny=y;
			if(x<A && S[x]==')') nx++;
			if(y<B && T[y]==')') ny++;
			if(i && hoge[x][y][i]+1<hoge[nx][ny][i-1]) {
				hoge[nx][ny][i-1]=hoge[x][y][i]+1;
				from[nx][ny][i-1]={x,y,i,')'};
			}
		}
	}
	
	x=A,y=B,i=0;
	while(hoge[x][y][i]) {
		s.push_back(from[x][y][i][3]);
		int nx=from[x][y][i][0];
		int ny=from[x][y][i][1];
		int ni=from[x][y][i][2];
		x=nx,y=ny,i=ni;
		
	}
	reverse(ALL(s));
	cout<<s<<endl;
	
}

まとめ

本番なんかこれ解けてないな。