codeforce每日一题
题目链接
题目分数:2200
题目描述
输入两个长度不超过 $200$ 的字符串 $s$ 和 $t$,只包含左右括号。输出 $s$ 和 $t$ 的最短公共超序列,要求这个超序列是一个合法括号字符串。(多解输出任意解。)
最短公共超序列
样例
输入样例1
(())(()
()))()
输出样例1
(())()()
输入样例2
)
((
输出样例2
(())
输入样例3
)
)))
输出样例3
((()))
输入样例4
())
(()(()(()(
输出样例4
(()()()(()()))
算法
(递归) $O(n*m)$
类似于记忆化搜索,我们先确定这一位是填$”(“$还是$”)”$,判断哪个得到的字符串最短,就选择哪个。$dfs$中的$k$代表当前$”(“$多于$”)”$的次数,$l$表示枚举$str1$的位数,$r$表示枚举$str2$的位数。我们用$ma$记忆每一次搜索的结果,避免重复搜索。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int ma[210][210][410];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(ma, -1, sizeof ma);
string str1, str2;
cin>>str1>>str2;
n = str1.size(), m = str2.size();
str1 += "!", str2 += "!";
int tmp = 0;
function<int(int,int,int)> dfs = [&](int l, int r, int k){
if(k > n + m) return INF;
if(l == n && r == m && !k) return 0;
if(ma[l][r][k]!=-1) return ma[l][r][k];
ma[l][r][k] = INF;
int res = dfs(l + (str1[l]=='('), r + (str2[r] == '('), k + 1) + 1;
if(k > 0) res = min(res, dfs(l + (str1[l] == ')'), r + (str2[r] == ')'), k - 1) + 1);
ma[l][r][k] = res;
return res;
};
string res;
function<void(int,int,int)> f = [&](int l, int r, int k){
if(l==n && r==m && !k) return;
if(dfs(l + (str1[l] == '('), r + (str2[r] == '('), k + 1) + 1 == dfs(l, r, k)){
res.push_back('(');
f(l + (str1[l] == '('), r + (str2[r] == '('), k + 1);
}else res.push_back(')'), f(l + (str1[l] == ')'), r + (str2[r] == ')'), k - 1);
};
f(0, 0, 0);
cout<<res<<endl;
return 0;
}