POJ 1141 Brackets Sequence-白红宇

POJ 1141 Brackets Sequence

阅读量：4325 次

发布时间：2019-06-06

本文共 1589 字，大约阅读时间需要 5 分钟。

题意：给出一个括号序列，问最短的补全成合法括号序列是什么。

解法：区间dp。考虑dp[i][j]表示i到j区间补全需要的多余字符个数，则有状态转移方程：dp[i][j] = min{dp[i][k], dp[k + 1][j]},0 <= k < j,if(s[i]s[j] == '()' or '[]') dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])。第一个方程意义为区间i到j的代价是区间i到k加区间k+1到j，枚举k，获得最优解，第二个方程意义为当s[i]和s[j]是一对匹配的括号的时候dp[i][j]就可以等于dp[i -1][j - 1]，这两种情况取min。因为要输出的是补全之后的字符串，所以要记录每次的选择，递归回去输出。

PS:不要多组输入！不要多组输入！不要多组输入！别问我怎么知道的……

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #define LL long longusing namespace std;int ans[105][105];//记录选择，如果是-1说明选择是第二种情况，否则表示第一种情况的kstring s;void dfs(int l, int r){ if(l > r) return ; if(l == r) { if(s[l] == '(' || s[l] == ')') printf("()"); else printf("[]"); return ; } if(ans[l][r] == -1) { printf("%c", s[l]); dfs(l + 1, r - 1); printf("%c", s[r]); } else { dfs(l, ans[l][r]); dfs(ans[l][r] + 1, r); }}int main(){ cin >> s; int dp[105][105] = {0}; for(int i = 0; i < 105; i++) for(int j = i; j < 105; j++) dp[i][j] = 1000000000; for(int i = 0; i < s.size(); i++) dp[i][i] = 1; for(int j = 0; j < s.size(); j++) for(int i = j - 1; i >= 0; i--) { if(s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')//第二种情况 { dp[i][j] = dp[i + 1][j - 1]; ans[i][j] = -1; } for(int k = i; k < j; k++)//第一种情况 { if(dp[i][j] > dp[i][k] + dp[k + 1][j]) { dp[i][j] = dp[i][k] + dp[k + 1][j]; ans[i][j] = k; } } } dfs(0, s.size() - 1); puts(""); return 0;}

转载于:https://www.cnblogs.com/Apro/p/4871452.html

你可能感兴趣的文章