POJ 1141 Brackets Sequence （区间DP + DFS ）

Brackets Sequence

Description

Let us define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. 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

()[()]

题目大意 ：输出输出包含给定序列的最短合法（成功配对）的括号序列

解题思路：想要达到最小的长度，关键在于找到合适的位置为不配对的符号配对。如何找到合适的位置呢？

                  对每一个合适的位置来说，如果从该处将字符串中断，两边所添加的字符总数将会最少。

                  所以也就是说要求出任意一段字符串所需要添加的字符数量（最小值）还有需要中断的位置。（有点分治的思想）

AC代码：

#include <iostream>
#define maxn 105
#define inf 0x3f3f3f3f
using namespace std;
int dp[maxn][maxn];// dp[i][j] -> 字符串中从i到j需要添加的最少字符数
int p[maxn][maxn];//  能获得最少dp[i][j]值时的中断位置
string s;
void oprint(int i, int j)
{
	if(i>j)	return;
	if(i==j){
		if(s[i]=='(' || s[i]==')')
			cout << "()";
		else
			cout << "[]";
	}
	else if(p[i][j] == -1){
		cout << s[i];
		oprint(i+1,j-1);
		cout << s[j];
	}
	else{
		oprint(i,p[i][j]);
		oprint(p[i][j]+1,j);
	}
}
int main()
{
    //freopen("test.txt","r",stdin);
	while(getline(cin,s))//使用getline读空行
	{
		if(s.length()==0){
			cout << endl;
			continue;
		}
		//memset(dp,0,sizeof(dp));
		int len = s.length();
		for(int i = 0; i<len; i++)
			dp[i][i] = 1;
		for(int i = len-1; i>=0; i--)
		{
			for(int j = i+1; j<len; j++)
			{
			    dp[i][j] = inf;//pay attention 必须将dp[i][j]初始化为无穷大
				if((s[i]=='('&&s[j]==')') || (s[i]=='['&&s[j]==']'))
				{
					dp[i][j] = dp[i+1][j-1];
					p[i][j] = -1;
					//continue; 这里一定不能使用continue
				}
				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];
						p[i][j] = k;
					}
				}
			}
		}
		oprint(0,len-1);
		cout << endl;
	}
	return 0;
}