POJ 1141 Brackets Sequence——区间dp

POJ 1141 Brackets Sequence——区间dp

这题和Uva 1626基本一样，我改变了一下枚举顺序以加深对区间dp的理解

#include #include #include #include using namespace std;const int maxn = 1000 + 10;char str[maxn], len;int dp[maxn][maxn];//闭区间void init(){ for (int i = 0; i <= len; i++) { dp[i + 1][i] = 0; dp[i][i] = 1; }}bool match(char a, char b){ if ( (a == '(' && b == ')') || (a == '[' && b == ']') ) return true; else return false;}void output(int j, int i){ if (j > i) return; if (j == i) { if (str[j] == '(' || str[j] == ')') printf("()"); else printf("[]"); return; } int temp = dp[j][i]; if (match(str[j], str[i]) && dp[j + 1][i - 1] == temp) { printf("%c", str[j]); output(j + 1, i - 1); printf("%c", str[i]); return; } for (int k = j; k < i; k++) { if (dp[j][k] + dp[k + 1][i] == temp) { output(j, k); output(k + 1, i); return; } }}int main(){ while(gets(str) != NULL) { len = strlen(str); init(); for (int i = 1; i < len; i++) { for (int j = i - 1; j >= 0; j--) { dp[j][i] = i - j + 1; if (match(str[j], str[i])) dp[j][i] = min(dp[j][i], dp[j + 1][i - 1]); for (int k = j; k < i; k++) { dp[j][i] = min(dp[j][i], dp[j][k] + dp[k + 1][i]); } //cout << j << " " << i << " " << dp[j][i] << endl; } } output(0, len - 1); cout << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。