博客

括号匹配（二）

  • Post author:
  • Post category:其他


时间限制：

1000

ms  |  内存限制：

65535

KB
难度：

6

描述

给你一个字符串，里面只包含”(“,”)”,”[“,”]”四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。

如：

[]是匹配的

([])[]是匹配的

((]是不匹配的

([)]是不匹配的
输入

第一行输入一个正整数N，表示测试数据组数(N<=10)

每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100

输出

对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行

样例输入

4
[]
([])[]
((]
([)]

样例输出

0
0
3
2



View Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<stdio.h>
 4 #define mx 102
 5 using namespace std;
 6 char ch[mx];
 7 int d[mx][mx];
 8 int min(int a,int b){return a<b? a:b;}
 9 int dp(int l,int r)
10 {    
11     int i,ans=10000000;
12     if(l==r)
13         return 1;
14     if(l>r)
15         return 0;
16     if(d[l][r]!=-1)
17         return d[l][r];
18     
19     if( (ch[l]=='('&&ch[r]==')') || (ch[l]=='['&&ch[r]==']') )
20     {
21         ans=min(ans,dp(l+1,r-1));
22     }
23     else 
24     {
25         ans=min(ans,dp(l+1,r)+1);
26         ans=min(ans,dp(l,r-1)+1);
27     }
28     for(i=l;i<r;i++)
29     {
30         ans=min(ans,dp(l,i)+dp(i+1,r));
31     }
32     d[l][r]=ans;
33     return ans;
34 }
35 int main()
36 {
37     int t,len,i,j;
38     scanf("%d",&t);
39     while(t--)
40     {
41         scanf("%s",ch);
42         len=strlen(ch);
43         for(i=0;i<len;i++)
44             for(j=0;j<len;j++)
45                 d[i][j]=-1;
46         printf("%d\n",dp(0,len-1));
47     }
48     return 0;
49 }


 

转载于:https://www.cnblogs.com/qijinbiao/archive/2012/02/23/2365356.html