POJ #1141 - Brackets Sequence - TODO: POJ website issue
A bottom-up DP. To be honest, it is not easy to relate DP to this problem. Maybe, all "most"\"least" problems can be solved using DP..
Reference: http://blog.sina.com.cn/s/blog_8e6023de01014ptz.html
There‘s an important details to AC: in case of "())", there are 2 solutions: ()() and (()). For the AC code, the former one is preferred.
1 // 1141 2 // http://blog.sina.com.cn/s/blog_8e6023de01014ptz.html 3 // 4 #include <stdio.h> 5 #include <string.h> 6 #include <memory.h> 7 8 #define MAX_LEN 101 9 10 bool isMatched(char *in, int i, int j) 11 { 12 return (in[i] == ‘(‘ && in[j] == ‘)‘) || (in[i] == ‘[‘ && in[j] == ‘]‘); 13 } 14 void printPath(int path[MAX_LEN][MAX_LEN], int i, int j, char in[MAX_LEN]) 15 { 16 int sInx = path[i][j]; 17 if (sInx == -1) 18 { 19 if (i == j) 20 { 21 //printf("Complete @ %d\n", i); 22 switch (in[i]) 23 { 24 case ‘(‘: 25 case ‘)‘: printf("()"); break; 26 case ‘[‘: 27 case ‘]‘: printf("[]"); break; 28 } 29 return; 30 } 31 else if (i + 1 == j) 32 { 33 //printf("Already matched: [%d, %d]\n", i, j); 34 printf("%c%c", in[i], in[j]); 35 return; 36 } 37 else if ((i+1) < j) 38 { 39 printf("%c", in[i]); 40 printPath(path, i + 1, j - 1, in); 41 printf("%c", in[j]); 42 } 43 } 44 else 45 { 46 printPath(path, 0, path[i][j], in); 47 //printf("Break @ %d\n", path[i][j], in); 48 printPath(path, path[i][j] + 1, j, in); 49 } 50 } 51 52 void calc(char in[MAX_LEN]) 53 { 54 unsigned slen = strlen(in); 55 if (slen == 0) 56 { 57 printf("\n"); 58 return; 59 } 60 else if (slen > 0) 61 { 62 int dp[MAX_LEN][MAX_LEN]; 63 int path[MAX_LEN][MAX_LEN]; 64 65 // Init 66 for (int i = 0; i < MAX_LEN; i ++) 67 for (int j = 0; j < MAX_LEN; j++) 68 { 69 dp[i][j] = 0xFFFFFF; 70 path[i][j] = -1; 71 } 72 73 // Def: dp[i][j] = min num of chars to add, from i to j 74 // Recurrence relation: 75 // 1. dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]), where k in (i..j) 76 // 2. dp[i][j] = dp[i+1][j-1], <IF in[i]:in[j] = [] or ()> 77 78 // i..j is range, k is interval 79 for (int k = 0; k < slen; k++) // NOTE: this is a bottom-up DP. We have to go from 0 to slen as interval 80 for (int i = 0, j = i + k; i < slen - k; i ++, j ++) 81 { 82 if (i == j) 83 { 84 dp[i][j] = 1; 85 path[i][j] = -1; 86 continue; 87 } 88 bool bIsMatched = isMatched(in, i, j); 89 if (bIsMatched) // eq 2 90 { 91 if (k == 1) // length == 2 92 { 93 dp[i][j] = 0; 94 path[i][j] = -1; 95 continue; 96 } 97 else if (k > 1) // length > 2 98 { 99 dp[i][j] = dp[i + 1][j - 1]; 100 path[i][j] = -1; // we don‘t split matched pair 101 // A: we still go ahead with eq1 102 } 103 } 104 //else // eq1 105 { 106 // t is iterator of split index 107 for (int t = i; t < j; t++) 108 { 109 int newVal = dp[i][t] + dp[t + 1][j]; 110 if (newVal <= dp[i][j]) // Label A: we prefer splitted solution 111 { 112 dp[i][j] = newVal; 113 path[i][j] = t; 114 } 115 } 116 } 117 } 118 printPath(path, 0, slen - 1, in); 119 } // if (slen > 0) 120 } 121 122 int main() 123 { 124 char in[MAX_LEN] = { 0 }; 125 gets(in); 126 calc(in); 127 printf("\n"); 128 return 0; 129 }
POJ #1141 - Brackets Sequence - TODO: POJ website issue,古老的榕树,5-wow.com
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。