#include <iostream>
#include <memory>
using namespace std;

const int MAX = 100;
char s[MAX];
int len;
bool calculated[MAX][MAX];
int d[MAX][MAX];
//ifstream cin("t.in");
//ofstream cout("t.out");

int min(int a, int b)
{
	return a > b ? b : a;
}

int bracket(int i, int j)
{
	if(calculated[i][j])
		return d[i][j];
	
	//to determine which model the string is and calculate its cost 
	int ans = 0xfffffff;
	if(i > j)
		return ans = 0;
	else if(i == j)
		return ans = 1;
	else
	{
		if(s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')
			ans = min(ans, bracket(i+1, j-1));
		if(s[i] == '(' || s[i] == '[')
			ans = min(ans, bracket(i+1, j) + 1);
		if(s[j] == ')' || s[j] == ']')
			ans = min(ans, bracket(i, j-1) + 1);
		for(int k = i; k <= j-1; k++)
			ans = min(ans, bracket(i, k) + bracket(k+1, j));
	}

	calculated[i][j] = true;
	d[i][j] = ans;
	return ans;
}

void print(int i, int j)
{
	if(i > j)
		return;
	if(i == j)
		switch (s[i])
		{
		case '(': cout<<"()"; return;
		case '[': cout<<"[]"; return;
		case ')': cout<<"()"; return;
		case ']': cout<<"[]"; return;
		}

	int ans = bracket(i, j);
	if((s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']') && (ans == bracket(i+1, j-1)))
	{
		cout<<s[i];
		print(i+1, j-1);
		cout<<s[j];
		return;
	}
	else if((s[i] == '(' || s[i] == '[') && (ans == bracket(i+1, j) + 1))
	{	
		if(s[i] == '(')
			cout<<"()";
		else cout<<"[]";
		print(i+1, j);
		return;
	}
	else if((s[j] == ')' || s[j] == ']') && ans == bracket(i, j - 1) + 1)
	{
		print(i, j-1);
		if(s[i] == ')')
			cout<<"()";
		else cout<<"[]";
		return;
	}
	for(int k = i; k < j; k++)
		if(ans == bracket(i, k) + bracket(k + 1, j))
		{
			print(i, k);
			print(k + 1, j);
		}
}

int main()
{
	//int n;
	//cin>>n;
	//for(int i = 0; i < n; i++)
	//{
	//	if(i)
	//		cout<<endl;
	//	char ch;
	//	cin.get(ch);
	//	cin.get(ch);
	//	len = 0;
	//	while(cin.get(ch) && ch != '\n')
	//		s[len++] = ch;
	//	memset(calculated, 0, len);
	//	print(0, len - 1);
	//	cout<<endl;
	//}
	while(cin>>s[len++]);
	print(0, len - 1);
	cout<<endl;
	return 0;
}

• Re:why wrong answer. It's time "Time Limit Exceeded" in zju (22) SWJT_hunanscyl 2006-12-10 11:04:36