首页 > 代码库 > UVa 1626 (输出方案) Brackets sequence

UVa 1626 (输出方案) Brackets sequence

2024-07-25 20:42:15   223人阅读

正规括号序列定义为：

  • 空序列是正规括号序列
  • 如果S是正规括号序列，那么[S]和(S)也是正规括号序列
  • 如果A和B都是正规括号序列，则AB也是正规括号序列

输入一个括号序列，添加尽量少的括号使之成为正规括号序列，并输出最优方案，多解的话输出任意一个即可。

设d(i, j)表示字符串s[i]~s[j]至少添加的括号的数量，则转移如下：

  • S形如[S‘]或(S‘)，则转移到d(i+1, j-1)
  • 如果S至少有两个字符，将其分为AB，转移到min{d(i, j), d(A) + d(B)}

不管是否满足第一条都要尝试第二种转移，因为[][]可能经过第一条转移到][

 

打印的时候重新检查一下最优决策。

 1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 const int maxn = 110; 8 char s[maxn]; 9 int d[maxn][maxn], n;10 11 bool match(char a, char b)12 {13     return (a == ‘(‘ && b == ‘)‘) || (a == ‘[‘ && b == ‘]‘);14 }15 16 void dp()17 {18     for (int i = 0; i < n; ++i)19     {20         d[i+1][i] = 0;    //对应空串21         d[i][i] = 1;22     }23     for (int i = n-2; i >= 0; --i)24     {25         for (int j = i+1; j < n; ++j)26         {27             d[i][j] = n;28             if(match(s[i], s[j]))29                 d[i][j] = min(d[i][j], d[i+1][j-1]);30             for (int k = i; k < j; ++k)31                 d[i][j] = min(d[i][j], d[i][k] + d[k+1][j]);32         }33     }34 }35 36 void print(int i, int j)37 {38     if(i > j)    return;39     if(i == j)40     {41         if(s[i] == ‘(‘ || s[i] == ‘)‘)    printf("()");42         else                            printf("[]");43         return;44     }45     int ans = d[i][j];46     if(match(s[i], s[j]) && ans == d[i+1][j-1])47     {48         printf("%c", s[i]);49         print(i+1, j-1);50         printf("%c", s[j]);51         return;52     }53     for (int k = i; k < j; ++k)54     {55         if(ans == d[i][k] + d[k+1][j])56         {57             print(i, k);58             print(k+1, j);59             return;60         }61     }62 }63 64 void readline(char* s)65 {66     fgets(s, maxn, stdin);67 }68 69 int main(void)70 {71     #ifdef    LOCAL72         freopen("1626in.txt", "r", stdin);73     #endif74     75     int T;76     readline(s);77     sscanf(s, "%d", &T);78     readline(s);79     while(T--)80     {81         readline(s);82         n = strlen(s) - 1;    //去掉最后的换行符 83         memset(d, -1, sizeof(d));84         dp();85         print(0, n-1);86         puts("");87         if(T)    puts("");88         readline(s);89     }90 91     return 0;92 }
代码君

 

UVa 1626 (输出方案) Brackets sequence


联系
我们