[NYIST15]括号匹配（二）（区间dp）-白红宇

[NYIST15]括号匹配（二）（区间dp）

阅读量：4687 次

发布时间：2019-06-09

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

题目链接：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=15

经典区间dp，首先枚举区间的大小和该区间的左边界，这时右边界也可计算出来。首先初始化一个匹配，那就是看看这两个括号是否匹配，即：

(s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']') ? dp(i,j) = dp(i+1,j-1)+2) : dp(i,j) = 0

接下来枚举i和j中间的所有点，更新dp(i,j)=max(dp(i,j), dp(i+m)+dp(m+1,j))寻找可能更优的匹配。

1 /* 2 ━━━━━┒ギリギリ♂ eye！ 3 ┓┏┓┏┓┃キリキリ♂ mind！ 4 ┛┗┛┗┛┃＼○／ 5 ┓┏┓┏┓┃ / 6 ┛┗┛┗┛┃ノ) 7 ┓┏┓┏┓┃ 8 ┛┗┛┗┛┃ 9 ┓┏┓┏┓┃10 ┛┗┛┗┛┃11 ┓┏┓┏┓┃12 ┛┗┛┗┛┃13 ┓┏┓┏┓┃14 ┃┃┃┃┃┃15 ┻┻┻┻┻┻16 */17 #include 
     
      18 #include 
      
       19 #include 
       
        20 #include 
        
         21 #include 
         
          22 #include 
          
           23 #include 
           
            24 #include 
            
             25 #include 
             
              26 #include 
              
               27 #include 
               
                28 #include 
                
                 29 #include 
                 
                  30 #include 
                  
                   31 #include 
                   
                    32 #include 
                    33 #include 
                     
                      34 using namespace std;35 #define fr first36 #define sc second37 #define cl clear38 #define BUG puts("here!!!")39 #define W(a) while(a--)40 #define pb(a) push_back(a)41 #define Rint(a) scanf("%d", &a)42 #define Rll(a) scanf("%I64d", &a)43 #define Rs(a) scanf("%s", a)44 #define Cin(a) cin >> a45 #define FRead() freopen("in", "r", stdin)46 #define FWrite() freopen("out", "w", stdout)47 #define Rep(i, len) for(int i = 0; i < (len); i++)48 #define For(i, a, len) for(int i = (a); i < (len); i++)49 #define Cls(a) memset((a), 0, sizeof(a))50 #define Clr(a, x) memset((a), (x), sizeof(a))51 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))52 #define lrt rt << 153 #define rrt rt << 1 | 154 #define pi 3.1415926535955 #define RT return56 #define lowbit(x) x & (-x)57 #define onenum(x) __builtin_popcount(x)58 typedef long long LL;59 typedef long double LD;60 typedef unsigned long long ULL;61 typedef pair
                      
                        pii;62 typedef pair
                       
                         psi;63 typedef pair
                        
                          pll;64 typedef map
                         
                           msi;65 typedef vector
                          
                            vi;66 typedef vector
                           
                             vl;67 typedef vector
                            
                              vvl;68 typedef vector
                             
                               vb;69 70 const int maxn = 1100;71 int dp[maxn][maxn];72 char s[maxn];73 int n;74 75 int main() {76 // FRead();77 int T;78 Rint(T);79 W(T) {80 Rs(s); n = strlen(s);81 Cls(dp);82 For(k, 2, n+1) {83 Rep(i, n-k+1) {84 dp[i][i+k-1] = 0;85 int j = i + k - 1;86 if((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')) {87 dp[i][j] = dp[i+1][j-1] + 2;88 }89 For(m, i, j) {90 dp[i][j] = max(dp[i][j], dp[i][m] + dp[m+1][j]);91 }92 }93 }94 printf("%d\n", n - dp[0][n-1]);95 }96 RT 0;97 }