甚至还不如我帅的链接嘤嘤嘤
这题，咱们真没什么好说的，先开看下这道题：括号匹配问题，既然我们已经求出最长的合法序列了，那么，用总长一减，极为要添加的括号数。
唯一需要注意的地方是两题的数据范围不一样大，需要将数组由105转至205；
这是代码哦~~（是的我承认我水了一题。。）
1 #include<set>
2 #include<map>
3 #include<list>
4 #include<queue>
5 #include<stack>
6 #include<string>
7 #include<cmath>
8 #include<ctime>
9 #include<vector>
10 #include<bitset>
11 #include<memory>
12 #include<utility>
13 #include<cstdio>
14 #include<sstream>
15 #include<iostream>
16 #include<cstdlib>
17 #include<cstring>
18 #include<algorithm>
19 using namespace std;
20
21 int z,y;
22 int dp[205][205];
23 string zy;
24
25 int ma(int a,int b){return a>b?a:b;}
26
27 int main(){
28 scanf("%d",&y);
29 while(y--){
30 cin>>zy;
31 if(zy[0]=='e'){
32 break;
33 }
34 z=zy.size();
35 memset(dp,0,sizeof(dp));
36 for(int l=1;l<z;l++){
37 for(int i=0,j=i+l;i<z-1&&j<z;i++,j=i+l){
38 if((zy[i]=='('&&zy[j]==')')||(zy[i]=='['&&zy[j]==']')){
39 dp[i][j]=dp[i+1][j-1]+2;
40 }
41 for(int k=i;k<=j;k++){
42 dp[i][j]=ma(dp[i][j],dp[i][k]+dp[k+1][j]);
43 }
44 }
45 }
46 printf("%d
",z-dp[0][z-1]);
47 }
48 return 0;
49 } 好的没得讲，新人开博鼓励一下吧~~