POJ 1141 解题报告

本文主要是介绍POJ 1141 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题是DP题。知道后思路倒是挺简单的，对于range [left, right]，尝试left < s <= right一个个填入对应的括号，看哪个最小选哪个。从长度为2依次填表即可。

多次WA，后来发现是数组给小了。我const int MAXN = 100;然后给'\0'留了个位置，但是估计有\n之类的也会scanf进去。开大后就过了。

完整的测试数据在这里：

https://neerc.ifmo.ru/past/2001/tests.rar

不用谢。

thestoryofsnow

1141

Accepted

240K

16MS

C++

2852B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj1141 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;
const int MAXN = 120;// print output in range [left, right] inclusive
void print(char str[], int brackets[], int left, int right, int S[][MAXN])
{if (left > right){return;}int s = S[left][right];if (brackets[left] < 0){printf("%c", str[left]);if (brackets[s] + brackets[left] == 0){print(str, brackets, left + 1, s - 1, S);printf("%c", str[s]);print(str, brackets, s + 1, right, S);}else{print(str, brackets, left + 1, s - 1, S);printf("%c", str[left] == '(' ? ')' : ']');print(str, brackets, s, right, S);	}}else{printf("%c", str[left] == ')' ? '(' : '[');printf("%c", str[left]);print(str, brackets, left + 1, right, S);}
}int main()
{// The input file contains at most 100 brackets (characters '(', ')', '[' and ']') // that are situated on a single line without any other characters among them.// e.g., "([(]"char str[MAXN];str[0] = '\0';int brackets[MAXN];// scanf("%s", str);gets(str);int len = strlen(str);for (int i = 0; i < len; ++i){if (str[i] == '('){brackets[i] = -1;}else if (str[i] == '['){brackets[i] = -2;}else if (str[i] == ')'){brackets[i] = 1;}else{// assert (str[i] == ']');brackets[i] = 2;}}int DP[MAXN][MAXN], S[MAXN][MAXN];// initialize DP with worst case: // add a corresponding bracket for each bracketfor (int left = 0; left < len; ++left){S[left][left] = left + 1;for (int right = left; right < len; ++right){DP[left][right] = 2 * (right - left + 1);}}for (int l = 2; l <= len; ++l){for (int left = 0; left + l - 1 < len; ++left){int right = left + l - 1;int minL = 2 + DP[left + 1][right], mins = left + 1, L;// if is left bracketif (brackets[left] < 0){for (int s = left + 1; s <= right; ++s){// if match left bracketif (brackets[s] + brackets[left] == 0){L = 1 + (left + 1 > s - 1 ? 0 : DP[left + 1][s - 1]) + 1 + (s + 1 > right ? 0 : DP[s + 1][right]);}// otherwise add a matching right bracketelse{L = 1 + (left + 1 > s - 1 ? 0 : DP[left + 1][s - 1]) + 1 + DP[s][right];}if (L < minL){minL = L;mins = s;}}}// otherwise if is right bracket, keep the initialized value// update DP and S for range [left, right]DP[left][right] = minL;S[left][right] = mins;}}print(str, brackets, 0, len - 1, S);printf("\n");return 0;  
}

这篇关于POJ 1141 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---