UVA 1626 Brackets sequence——dp

UVA 1626 Brackets sequence——dp

印象中第5遍了。。。。。。换行卡的挺严，嗯

#include #include #include #include using namespace std;const int maxn = 200;const int INF = 0x3f3f3f3f;int T;char str[maxn];int n, dp[maxn][maxn];bool judge(int i, int j) { if ((str[i]=='['&&str[j]==']')||(str[i]=='('&&str[j]==')')) return true; return false;}void print(int x, int y) { if (x > y) return; if (x == y) { if (str[x] == '[' || str[x] == ']') printf("[]"); else if (str[x] == '(' || str[x] == ')') printf("()"); return; } if (judge(x, y) && dp[x][y] == dp[x+1][y-1]) { printf("%c", str[x]); print(x+1, y-1); printf("%c", str[y]); return; } for (int k = x; k < y; k++) { if (dp[x][y] == dp[x][k]+dp[k+1][y]) { print(x, k); print(k+1, y); return; } }}int main() { //freopen("out.txt", "w", stdout); scanf("%d", &T); getchar(); for (int kase = 1; kase <= T; kase++) { getchar(); gets(str+1); n = strlen(str+1); for (int i = 1; i <= n; i++) dp[i][i-1] = 0, dp[i][i] = 1; for (int len = 2; len <= n; len++) { for (int i = 1; i+len-1 <= n; i++) { int j = i+len-1; dp[i][j] = INF; if (judge(i, j)) 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]); } } } if (kase != 1) printf("\n"); print(1, n); printf("\n"); } return 0;}

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