題意：給定一個括號序列，將它變成匹配的括號序列，可能多種答案任意輸出一組即可。注意：輸入可能是空串。

   思路：D[i][j]表示區間[i, j]至少需要匹配的括號數，轉移方程D[i][j] = min(D[i][k] + D[k+1][j], D[i][j]).

    輸入時，可能是空串應該用gets、fgets、getline，應注意換行符的吸收。每組數據前有一個換行符，輸出的兩組數據之間有換行。

AC代碼：

#include<cstdio>#include<vector>#include<algorithm>#include<cstring>#include<utility>#include<string>#include<iostream>using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define  PI pair<int, int> const int maxn = 100 + 5;char s[maxn];int d[maxn][maxn];bool match(char a, char b) {	if(a == '(' && b == ')' || a == '[' && b == ']') return true;	return false;}void PRint(int i, int j) {	if(i > j) return;	if(i == j) {		if(s[i] == '(' || s[i] == ')') printf("()");		else printf("[]");	}	int ans = d[i][j];	if(match(s[i], s[j]) && d[i+1][j-1] == ans) {		printf("%c", s[i]); 		print(i+1, j-1);		printf("%c", s[j]);		return;	}	for(int k = i; k < j; ++k) {		if(d[i][k] + d[k+1][j] == ans) {			print(i, k);			print(k+1, j);			return;		}	}}void solve(int n) {	//初始化邊界	for(int i = 0; i < n; ++i) {		d[i + 1][i] = 0;		d[i][i] = 1;	}	for(int i = n - 2; i >= 0; --i) 		for(int j = i + 1; j < n; ++j) {			d[i][j] = n;  //最多需要匹配N個括號 			if(match(s[i], s[j])) d[i][j] = min(d[i][j], d[i+1][j-1]);			for(int k = i; k < j; ++k) {				d[i][j] = min(d[i][k] + d[k+1][j], d[i][j]);			}	}	print(0, n - 1);}int main() {	int T;	scanf("%d", &T);	getchar();	int kase = 0;	while(T--){		if(kase++) {			printf("/n"); 		} 		getchar();		fgets(s, sizeof(s), stdin);		int n = strlen(s);		if(n == 1) {			printf("/n");			continue; //空串		}		solve(n - 1);		printf("/n");	}	return 0;}如有不當之處歡迎指出！