本文主要是介绍POJ - 1141 Brackets Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【问题描述】
定义如下规则序列(字符串)：
1．空序列是规则序列；
2．如果S是规则序列，那么(S)和[S]也是规则序列；
3．如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
()，[]，(())，([])，()[]，()[()]
而以下几个则不是：
(，[，]，)(，())，([()
现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列略……
【输入】
输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。
【输出】
输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。
思路：区间DP，由于计算d[i,j]需要知道d[i+1,j],d[i,j-1],d[i+1,j-1],所以按照j-i递增的顺序计算d[i,j]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;char s[MAXN];
int dp[MAXN][MAXN],key[MAXN][MAXN];
int n;void DP(){for (int i = 0; i < n; i++)dp[i][i] = 1;for (int len = 1; len < n; len++)for (int i = 0; i < n - len; i++){int j = i + len;dp[i][j] = 0x3f3f3f3f;if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')){dp[i][j] = dp[i+1][j-1];key[i][j] = -1;}for (int k = i; k < j; k++)if (dp[i][j] > dp[i][k] + dp[k+1][j]){dp[i][j] = dp[i][k] + dp[k+1][j];key[i][j] = k;}}
}void print(int l,int r){if (l > r)return;if (l == r){if (s[l] == '(' || s[l] == ')')printf("()");else if (s[l] == '[' || s[l] == ']')printf("[]");}else if (key[l][r] == -1){printf("%c",s[l]);print(l+1,r-1);printf("%c",s[r]);}else {print(l,key[l][r]);print(key[l][r]+1,r);}
}int main(){while (gets(s)){n = strlen(s);DP();print(0,n-1);printf("\n");}return 0;
}这篇关于POJ - 1141 Brackets Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
