例题9-10 括号序列 UVa1626 - c++编程基础

TOP

例题9-10 括号序列 UVa1626

2015-07-20 17:16:36 来源: 作者: 【大中小】浏览:2次

1.题目描述：点击打开链接

2.解题思路：本题要求添加尽量少的括号，使得括号序列是一个正规序列。定义d(i,j)表示子串S[i...j]至少需要添加几个括号。根据题意，可知有两种转移方式：

（1）如果S形如(S‘)或[S'],则转移到d(S')；

（2）如果S至少有两个字符，则可以分成AB，转移到d(A)+d(B)；

边界是：S为空时，d(S)=0，S为单字符时，d(S)=1,。注意不管S是否满足第一条，都要尝试第二种转移方式。否则"[][]"会被转移到"]["，然后只能加两个括号了。本题打印的时候需要重新检查哪个决策最好。好处是节约空间，坏处是打印时代码比较复杂，速度较慢。但由于只有少数需要打印，因此基本可以忽略不计。

3.代码：

#define _CRT_SECURE_NO_WARNINGS 
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   using namespace std; #define maxn 200+10 int T, n; string S; int d[maxn][maxn];//表示S[i...j]至少需要填上几个括号（闭区间） bool match(char p, char q) { if (p == '('&&q == ')')return true; if (p == '['&&q == ']')return true; return false; } void dp() { for (int i = 0; i < n; i++) { d[i + 1][i] = 0;//空串 d[i][i] = 1;//单字符 } for (int i = n - 2; i >= 0; i--)//起点逆序枚举 for (int j = i + 1; j < n; j++)//终点顺序枚举，保证子区间已经计算过 { d[i][j] = n; if (match(S[i], S[j])) d[i][j] = min(d[i][j], d[i + 1][j - 1]);//第一种转移方式 for (int k = i; k < j; k++) d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j]);//第二种转移方式 } } void print(int i, int j)//分三种独立情况，每次都只执行一种便返回 { if (i>j)return; if (i == j)//单字符 { if (S[i] == '(' || S[i] == ')') printf("()"); else printf("[]"); return; } int ans = d[i][j]; if (match(S[i], S[j]) && ans == d[i + 1][j - 1])//第一种转移情况 { printf("%c", S[i]); print(i + 1, j - 1); printf("%c", S[j]); return; } for (int k = i; k < j; k++)//第二种转移情况 if (ans == d[i][k] + d[k + 1][j]) { print(i, k); print(k + 1, j); return; } } int main() { //freopen("test.txt", "r", stdin); cin >> T; getchar(); while (T--) { getchar(); getline(cin, S); n = S.length(); dp(); print(0, n - 1); puts(""); if (T)cout << endl; } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：uva 10954 Add All（排序）	下一篇：uva 10603 Fill （BFS）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: