本文主要是介绍uva-1626 Brackets sequence 区间dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给一个只含有()[]的序列添加最少的符号使括号成为正规序列
如果s可以分成[s']或(s')则转移到s'状态，然后对于区间[j, l]将区间分成两部分, dp[j][l] = min(dp[j][l], dp[j][k] + dp[k + 1][l]), j < k < l;
在处理过程中用c[i][j]记录区间[i, j]最优的分割点， 如果值为-1表示按第一种方式转移最佳，借助c数组递归输出最优解。
#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
int dp[110][110], c[110][110];
char s[110];
void dfs(int b, int e) {if(b > e)return;if(b == e) {if(s[b] == '(' || s[b] == ')')printf("()");else printf("[]");}else if(c[b][e] == -1) {printf("%c", s[b]);dfs(b + 1, e - 1);printf("%c", s[e]);}else {dfs(b, c[b][e]);dfs(c[b][e] + 1, e);}
}
int main() {int t, n, i, j, k;scanf("%d%*c", &t);while(t--) {getchar();gets(s);n = strlen(s);memset(dp, 0, sizeof(dp));memset(c, -1, sizeof(c));for(i = 0; i < n; i++)dp[i][i] = 1;for(i = 1; i < n; i++) {for(j = 0; j < n - i; j++) {int l = j + i;if((s[j] == '(' && s[l] == ')') || (s[j] == '[' && s[l] == ']'))dp[j][l] = dp[j + 1][l - 1];else dp[j][l] = INF;for(k = j; k < l; k++) {if(dp[j][l] > dp[j][k] + dp[k + 1][l]) {dp[j][l] = dp[j][k] + dp[k + 1][l];c[j][l] = k;}}}}dfs(0, n - 1);printf("\n");if(t) printf("\n");}return 0;
}这篇关于uva-1626 Brackets sequence 区间dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
