#C240805A. 括号
网址（Website）
题目（Problem）
题目描述
定义一个括号序列：
- 一个空序列是括号序列；
- 如果
S是括号序列，那(S)和[S]也是括号序列。 - 如果
S和T都是括号序列，那么ST也是括号序列。
例如：(),[],(()),([]),()[],()[()]都是括号序列。
而(,[,],)(,([))不是
现在给定了一个由 [,],(,) 构成的序列，请添加最少的括号使得其变成一个括号序列。
输入格式
输入一行一个字符串 $S$ 表示初始序列。
输出格式
输出一行一个字符串表示合法括号序列。如果有多个满足条件的方案，输出任意一个。
输入样例：
([(]输出样例：
()[()]题解（Solution）
这道题的数据范围很小。
根据做题经验，我们考虑用动态规划求出最小的答案，令 $f[i][j]$ 表示区间 $[i,j]$ 补成合法的括号序列的最小方案数，分情况考虑：
(S)或[S]的情况：如果$s[i]==s[j]$，则有$f[i][j]=max(f[i][j],f[i+1][j-1])$；AB的情况：方案数就是将两个区间分别的方案合并，即 $f[i][j]=max(f[i][j],f[i][k]+f[k+1][j])$；(S或S)的情况：直接补全括号，这里可以直接把 $f[i][i]$ 设为 $1$ ，将这种情况包含到情况2即可。
求出最小方案数后，我们再考虑如何给出一种方案。由上面的转化式可知：
- 如果当前的 $f[i][j]$ 为 $f[i+1][j-1]$ 且 $s[i]==s[j]$ ，则我们只需要考虑 $[i+1,j-1]$ 就可以了；
- 如果存在 $f[i][j]=max(f[i][j],f[i][k]+f[k+1][j])$，我们分成区间 $[i,k]$ 和 $[k+1,j]$ 考虑；
- 如果当前区间 $[i,j]$ 有 $i==j$ ，那么直接看当前的 $s[i]$ 为多少，并且补全这个括号即可。
时间复杂度：$O(n^3)$
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define fi first
#define se second
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 105;
int n,f[N][N];
char s[N];
void dfs(int l,int r){
if(l>r) return;
if(l==r){
if(s[l]=='('||s[r]==')') cout<<"()";
if(s[l]=='['||s[r]==']') cout<<"[]";
return;
}
if(((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))&&f[l][r]==f[l+1][r-1]){
cout<<s[l];
dfs(l+1,r-1);
cout<<s[r];
}else{
For(k,l,r-1){
if(f[l][r] == f[l][k]+f[k+1][r])
return dfs(l,k),dfs(k+1,r);
}
}
}
//注意！！！不能直接使用memset赋值,因为遇到"()"的情况f[l][r]=0而不是inf
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>(s+1);int Tim = clock();
n = strlen(s+1);
Rof(i,n,1){//枚举左区间
f[i][i] = 1;
For(j,i+1,n){
f[i][j] = inf;
if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))
f[i][j] = f[i+1][j-1];
For(k,i,j-1)
f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]);
}
}dfs(1,n);cout<<'\n';
cerr<<f[1][n]<<'\n';
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
