题意
咕咕是一只神奇的咕咕，虽然他很讨厌字符串但是他喜欢看别人做字符串的题目，现在咕咕给了你一个只含有'(’ 和‘)’和'['和']'的字符串，现在让你把他变成正则序列。
正则序列：
- 空序列是正则序列。
- 如果S是正则序列，那么(S)和[S]也是。
- 如果A是B也是，那么AB也是正则序列。
输入一个只含有'(', ')', '[', ']'字符的字符串，字符串的最大长度是100。
输出最少需要多少次变换后的序列（需要换行）。
分析
设 \(dp[l][r]\) 为将区间 \([l,r]\) 变成括号匹配的序列最少需要的代价。
对于 (())（左右的 _ 表示当前需要填写的括号）。此时 \(dp[l][r]\) 就能从 \(dp[l + 1][r - 1]\) 转移过来。这对应的是第二条规则。
对于第三条规则，只需要在 \([l,r]\) 中枚举一个 \(k\)，即枚举一下从哪里断开，分成两个正则序列。
转移的时候需要记录一下每个状态的最优决策点在哪里，便于接下来的递归输出。
总的dp方程如下：
\[dp[l][r] = min(dp[l][r],min(dp[l + 1][r - 1],dp[l][k] + dp[k + 1][r]))
\]
然后递归输出就行了。
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int MAXN = 2e3;
const int INF = 1e9;
string s;
int dp[MAXN][MAXN],pos[MAXN][MAXN];
void print(int i,int j){
if(i > j)return;
if(i == j){
if(s[i] == '(' || s[i] == ')')cout << "()";
else if(s[i] == '[' || s[i] == ']')cout << "[]";
return;
}
if(pos[i][j] == -1){
cout << s[i];
print(i + 1,j - 1);
cout << s[j];
}
else if(pos[i][j] != -1){
print(i,pos[i][j]);
print(pos[i][j] + 1,j);
}
}
int main(){
while(getline(cin,s)){
if(s.size() == 0){
puts("");
continue;
}
memset(dp,0,sizeof dp);
memset(pos,0,sizeof pos);
for(int i = 0; i < s.size(); i++){
dp[i][i] = 1;
}
for(int l = 1; l < s.size(); l++){
for(int i = 0; i + l < s.size(); i++){
int j = i + l;
dp[i][j] = INF;
if(s[i] == '(' && s[j] == ')'){
dp[i][j] = min(dp[i][j],dp[i + 1][j - 1]);
pos[i][j] = -1;
}
else if(s[i] == '[' && s[j] == ']'){
dp[i][j] = min(dp[i][j],dp[i + 1][j - 1]);
pos[i][j] = -1;
}
for(int k = i; k < j; k++){
if(dp[i][j] > dp[i][k] + dp[k + 1][j]){
dp[i][j] = dp[i][k] + dp[k + 1][j];
pos[i][j] = k;
}
}
}
}
print(0,s.size() - 1);
puts("");
}
}