UVa 1626 括号序列——区间DP

UVa 1626 括号序列——区间DP

这题坑在输入输出，注意输入时两两之间有空行，输出时两两之间也有空行，而且紫书上的输出函数执行后时不带换行的

#include #include #include #include #include using namespace std;char str[110];int dp[110][110];//表示闭区间[i,j]需要添加的最小括号数int n;//str长度bool match(char a, char b){ if (a == '(' && b == ')') return true; if (a == '[' && b == ']') return true; return false;}void DP() { for (int i = 0; i < n; i++) { dp[i + 1][i] = 0; dp[i][i] = 1; } for (int i = n - 2; i >= 0; i--) { for (int j = i + 1; j < n; j++) { dp[i][j] = j - i + 1; if (match(str[i], str[j])) { dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]); } for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]); } } }}void output(int i, int j) { if (i > j) return; if (i == j) { if (str[i] == '(' || str[i] == ')') { printf("()"); } else printf("[]"); return; } int ans = dp[i][j]; if (match(str[i], str[j]) && ans == dp[i + 1][j - 1]) { printf("%c", str[i]); output(i + 1, j - 1); printf("%c", str[j]); return; } for (int k = i; k < j; k++) { if (ans == dp[i][k] + dp[k + 1][j]) { output(i, k); output(k + 1, j); return; } }}int main(){ int T; scanf("%d", &T); getchar(); int flag = 0; while (T--) { getchar(); gets(str); n = strlen(str); DP(); if (flag++) printf("\n"); output(0, n - 1); printf("\n"); } return 0;}

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