本文主要是介绍POJ 1141 Brackets Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ 1141;链接：http://poj.org/problem?id=1141
题目：
Brackets Sequence
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 23638 | Accepted: 6665 | Special Judge | ||
Description
Let us define a regular brackets sequence in the following way:
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
Input
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample Input
([(]
Sample Output
()[()]
题目分析：
用dp得到记忆表path[][],用递归求出最短的合法序列。
注意点：建议用gets（）来读入字符串，因为测试数据中有空行，如果用scanf（）或者cin读不到空格（太坑，因为这个wa了很多次）；
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int MAXN = 110;
char str[MAXN];
int dp[MAXN][MAXN], path[MAXN][MAXN];void oprint(int i, int j)
{if(i > j) return ;if(i == j){if('[' == str[i] || ']' == str[i])cout << "[]";elsecout << "()";}else {if(-1 == path[i][j]){cout << str[i];oprint(i + 1, j - 1);cout << str[j];}else{oprint(i, path[i][j]);oprint(path[i][j]+1, j);}}
}int main()
{std::ios::sync_with_stdio(false);while(gets(str)){int n = strlen(str);if(0 == n) {cout << endl;continue;}memset(dp, 0, sizeof(dp));memset(path, 0, sizeof(path));for(int i = 0; i < n; i++)dp[i][i] = 1;for(int r = 1; r < n; r++){for(int i = 0; i < n - r; i++){int j = i + r;dp[i][j] = 0x7fffffff;if( ('(' == str[i] && ')' == str[j]) || ('[' == str[i] && ']' == str[j]) ){dp[i][j] = dp[i + 1][j - 1];path[i][j] = -1;// continue;//不能有continue}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];path[i][j] = k;}}}}oprint(0, n - 1);cout << endl;}return 0;
}
这篇关于POJ 1141 Brackets Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
