기억 검색(DP+DFS) URAL 1183 Brackets Sequence
10971 단어 sequence
제목 전송문
1 /* 2 (DP+DFS):dp[i][j] i j , 3 dp[x][x] = 1 ;dp[x][y] = 0, x > y; 4 s[x] s[y] , (x+1, y-1); x~y-1 , 5 */ 6 #include <cstdio> 7 #include <algorithm> 8 #include <cmath> 9 #include <iostream> 10 #include <cstring> 11 using namespace std; 12 13 const int MAXN = 1e2 + 10; 14 const int INF = 0x3f3f3f3f; 15 int dp[MAXN][MAXN]; 16 int pos[MAXN][MAXN]; 17 char s[MAXN]; 18 19 void DFS(int x, int y) 20 { 21 if (dp[x][y] != -1) return ; 22 if (x > y) {dp[x][y] = 0; return ;} 23 if (x == y) {dp[x][y] = 1; return ;} 24 25 dp[x][y] = INF; 26 if ((s[x]=='(' && s[y]==')') || (s[x]=='[' && s[y]==']')) 27 { 28 pos[x][y] = -1; 29 DFS (x+1, y-1); 30 dp[x][y] = dp[x+1][y-1]; 31 } 32 for (int i=x; i<y; ++i) 33 { 34 DFS (x, i); DFS (i+1, y); 35 int cur = dp[x][i] + dp[i+1][y]; 36 if (cur < dp[x][y]) 37 { 38 dp[x][y] = cur; pos[x][y] = i; 39 } 40 } 41 } 42 43 void print(int x, int y) 44 { 45 if (x > y) return ; 46 if (x == y) 47 { 48 if (s[x] == '(' || s[y] == ')') printf ("()"); 49 else printf ("[]"); 50 return ; 51 } 52 if (pos[x][y] == -1) 53 { 54 printf ("%c", s[x]); 55 print (x+1, y-1); 56 printf ("%c", s[y]); 57 } 58 else 59 { 60 print (x, pos[x][y]); print (pos[x][y]+1, y); 61 } 62 } 63 64 int main(void) //URAL 1183 Brackets Sequence 65 { 66 //freopen ("O.in", "r", stdin); 67 68 while (scanf ("%s", s+1) == 1) 69 { 70 int len = strlen (s+1); 71 memset (dp, -1, sizeof (dp)); 72 memset (pos, 0, sizeof (pos)); 73 74 DFS (1, len); 75 print (1, len); puts (""); 76 } 77 78 return 0; 79 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2442 SequenceSequence Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 6120 Accepted: 1897 Description Given m sequences, e...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.