UVA 1626 Brackets sequence 区间DP

    题意：给定一个括号序列，将它变成匹配的括号序列，可能多种答案任意输出一组即可。注意：输入可能是空串。

   思路：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;}如有不当之处欢迎指出！