POJ 1141 / UVa 1626 Brackets Sequence (区间DP&打印路径)

/*0ms,416KB*/

#include<cstdio>
#include<cstring>
const int mx = 100;

char s[mx];
int dp[mx][mx];///最小添加个数
int divide_pos[mx][mx];///满足最小添加个数的添加括号的位置

void interval_DP(int len)
{
	int l, i, j, k;
	for (i = 0; i < len; ++i) dp[i][i] = 1;
	for (l = 1; l < len; ++l)
		for (i = 0; i < len - l; i++)
		{
			j = i + l;
			dp[i][j] = mx;
			if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))
				dp[i][j] = dp[i + 1][j - 1], divide_pos[i][j] = -1;
			for (k = i; k < j; ++k)
				if (dp[i][k] + dp[k + 1][j] < dp[i][j])
					dp[i][j] = dp[i][k] + dp[k + 1][j], divide_pos[i][j] = k;
		}
}

void print(int i, int j)
{
	if (i > j) return;
	if (i == j)
	{
		if (s[i] == '(' || s[i] == ')') printf("()");
		else printf("[]");
		return;
	}
	if (divide_pos[i][j] == -1)///说明这段无需添加括号
	{
		putchar(s[i]);
		print(i + 1, j - 1);
		putchar(s[j]);
		return;
	}
	print(i, divide_pos[i][j]);
	print(divide_pos[i][j] + 1, j);
}

int main()
{
	scanf("%s", s);
	int len = strlen(s);
	interval_DP(len);
	print(0, len - 1);
	putchar(10);
	return 0;
}