题目传送门
Description
Let us define a regular brackets sequence in the following way:
- Empty sequence is a regular sequence.
- If S is a regular sequence, then (S) and [S] are both regular sequences.
- If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters ‘(’, ‘)’, ‘[’, and ‘]’ is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 … an is called a subsequence of the string b1 b2 … bm, if there exist such indices 1 = i1 < i2 < … < in = m, that aj = bij for all 1 = j = n.
Input
The input file contains at most 100 brackets (characters ‘(’, ‘)’, ‘[’ and ‘]’) that are situated on a single line without any other characters among them.
Output
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample Input
([(]
Sample Output
()[()]
题意：
给出一个由(、)、[、]组成的字符串，添加最少的括号使得所有的括号匹配，输出最后得到的字符串。
注意空行符合题意
题解：
-
POJ 2955 括号匹配的升级版，多了打印路径
-
定义dp[i][j]：区间i->j最少需要加多少括号才能成为合法序列
v[i][j]：记录一段区间是在哪里断开最优，如果没有则为-1 -
i==j d[i][j] = 1 s[i] == ‘(’ && s[j] == ‘)’
或者 s[i] == ‘[’ && s[j] == ']'d[i][j] = d[i+1][j-1] 否则 d[i][j] = min{d[i][k] + d[k+1][j]}
i<=k<j ， v[i][j]记录断开的位置k采用递推方式计算d[i][j]
-
输出结果时采用递归方式输出print(0, len-1)
输出函数定义为print(int i, int j)，表示输出从下标i到下标j的合法序列
| i>j | 直接返回，不需要输出 |
|---|---|
| 当i==j时（d[i][j]为1，至少要加一个括号） | 如果s[i]为’(’ 或者’)’，输出"()"，否则输出"[]" |
| v[i][j] == -1（说明i和j匹配） | cout << “[” print(i+1, j-1) cout << "]" |
| 否则（i->j区间断开） | 递归子区间 print(i, v[i][j]) print(v[i][j]+1, j) |
AC-Code:
#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <fstream>
#include <set>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;const int INF = 0x7fffffff;
const int MAXN = 102;int dp[MAXN][MAXN];// 区间i->j最少需要加多少括号才能成为合法序列
int v[MAXN][MAXN];//记录一段区间是在哪里断开最优，是为了记录路径，打印括号
string s;
bool check(char a, int b)
{
if (a == '(' && b == ')') return true;else if (a == '[' && b == ']') return true;else return false;
}
void dfs(int i, int j) {
if (i > j)return;else if (i == j) {
if (s[i] == '(' || s[i] == ')')printf("()");elseprintf("[]");}else if (v[i][j] == -1) {
printf("%c", s[i]);dfs(i + 1, j - 1);printf("%c", s[j]);}else {
dfs(i, v[i][j]);dfs(v[i][j] + 1, j);}
}
int main() {
while (getline(cin, s)) {
int L = s.length();fill(dp[0], dp[0] + L * MAXN + 1, INF);//初始化为INFfor (int i = 0; i < L; i++) {
dp[i][i] = 1;dp[i + 1][i] = 0;}for (int len = 1; len < L; len++)for (int i = 0; i < L - len; i++) {
int j = i + len;if (j > L)break;if (check(s[i], s[j])) {
dp[i][j] = dp[i + 1][j - 1]; //当前匹配的话，就不需要增加字符v[i][j] = -1;}for (int k = i; k < j; k++) {
// 即使i,j匹配也不能省略if (dp[i][k] + dp[k + 1][j] < dp[i][j]) {
dp[i][j] = dp[i][k] + dp[k + 1][j];v[i][j] = k;}}}dfs(0, L - 1);printf("\n");}return 0;
}