[CF1272F]Two Bracket Sequences

题干很短就不翻译了......
首先考虑如果构造的括号序列不一定合法的话，那就是一道算S和T串的编辑距离的题了。而这个题要求我们构造出来的括号序列合法，就考虑怎么样才能使括号序列合法：
首先，考虑一个一个构造，那么未匹配的右括号肯定是不能存在的，否则必然不合法；
然后，就要考虑未匹配的左括号的个数了；因为这些左括号肯定需要额外构造相应的右括号才能使括号序列合法。
于是就可以在剩余的左括号上面做文章：
设$dp[i][j][k]$表示当前匹配到了S串的第$i$个位置，T串的第$j$个位置，未匹配的左括号个数为$k$。那么就要考虑几种情况：
1.如果我在这里构造一个左括号，那么未匹配的左括号数量+1。然后还要考虑S串的这个位置是不是左括号或者右括号，也就是匹配数是否有变化。于是可以写出方程：$dp[i][j][k]=min(dp[i][j][k],dp[i-(s[i-1]=='(')][j-(t[j-1]=='('][k-1])$；
2.如果我在这里构造一个右括号，那么未匹配的右括号数量-1。剩下的类似，于是就有另外一个dp方程：$dp[i][j][k]=min(dp[i][j][k],dp[i-(s[i-1]==')')][j-(t[j-1]==')')][k+1])$。
然后再在$dp[i][j][k]+k$中找个最小值就行了
而这道题要输出方案，记录一个前驱就行。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int N=210;
const int inf=0x3f3f3f3f;
char s[N],t[N];
int n,m;
int dp[N][N][N*2];
struct state
{
    int i,j,k;
    state(){}
    state(int _i,int _j,int _k):i(_i),j(_j),k(_k){}
};
state pre[N][N][N*2];
string ans;
inline void upd(int i,int j,int k,int _i,int _j,int _k)
{
    if(_i<0||_j<0||_i>n||_j>m||_k>n+m||_k<0)return;
    if(dp[i][j][k]>dp[_i][_j][_k]+1)
    {
        dp[i][j][k]=dp[_i][_j][_k]+1;
        pre[i][j][k]=state(_i,_j,_k);
    }
}
int main()
{
    scanf(
    scanf(
    n=strlen(s),m=strlen(t);
    mem(dp,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<=n+m;++k)
            {
                upd(i,j,k,i-(i&&s[i-1]=='('),j-(j&&t[j-1]=='('),k-1);
                upd(i,j,k,i-(i&&s[i-1]==')'),j-(j&&t[j-1]==')'),k+1);
            }
        }
    }
    int p1=n,p2=m,pk=0;
    for(int k=0;k<=n+m;++k)
    {
        if(dp[n][m][pk]+pk>dp[n][m][k]+k)
        {
            pk=k;
        }
    }
    for(int i=0;i<pk;++i)ans+=")";
    while(p1||p2||pk)
    {
        state now=pre[p1][p2][pk];
        if(pk==now.k)ans+=")(";
        else if(pk<now.k)ans+=")";
        else ans+="(";
        p1=now.i;p2=now.j;pk=now.k;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    return 0;
}