CF1272F Two Bracket Sequences

题意：
  求一个最短的合法的由 ( 和 ) 构成的字符串，且两个给定的由 ( 和 ) 构成的字符串是它的子序列。\((length<=200)\)

思路：
  合法就是指要先有 ( 再有 ) ，并且 ( 和 ) 数量相同。那么根据数据范围，可以考虑使用DP，并且在记录字符串长度的同时，还要记录 ( 的数量。

  那么递推式也就是判断一下当前这个字符是否和生成字符串里的字符相同就行了。
  为了减小复杂度，用了记忆化搜索。

#include <bits/stdc++.h>
#include <cstring>
using namespace std;
const int INF = 1e9 + 7;

int slen, tlen;
int dp[210][210][410];
char s[210], t[210];
char ji[210][210][410];

inline int search(int i, int j, int k)
{
    if (k < 0 || k > 400)
        return INF;
    if (dp[i][j][k] != -1)
        return dp[i][j][k];
    if (i > slen && j > tlen)
        return k;
    int le = search(i + (i <= slen && s[i] == '('), j + (j <= tlen && t[j] == '('), k + 1) + 1;
    int ri = search(i + (i <= slen && s[i] == ')'), j + (j <= tlen && t[j] == ')'), k - 1) + 1;
    ji[i][j][k] = le < ri ? '(' : ')';
    return dp[i][j][k] = min(le, ri);
}

int main()
{
    memset(dp, -1, sizeof dp);
    scanf("%s%s", s + 1, t + 1);
    slen = strlen(s + 1);
    tlen = strlen(t + 1);
    int ans = search(1, 1, 0), le = 1, ri = 1, _k = 0;
    while (le <= slen || ri <= tlen)
    {
        printf("%c", ji[le][ri][_k]);
        if (ji[le][ri][_k] == '(')
            le += (le <= slen && s[le] == '('), ri += (ri <= tlen && t[ri] == '('), ++_k;
        else
            le += (le <= slen && s[le] == ')'), ri += (ri <= tlen && t[ri] == ')'), --_k;
    }
    while (_k--)
        putchar(')');
    //printf("%d", ans);
    return 0;
}