内存限制:64MB 时间限制:1000ms 特判: No

通过数:54 提交数:158 难度:6

题目描述:

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

如：

[]是匹配的

([])[]是匹配的

((]是不匹配的

([)]是不匹配的

输入描述:

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

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

输出描述:

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

样例输入:

4

[]

([])[]

((]

([)]

样例输出:

0

0

3

2

思路

用$dp[i][j]$储存$i$到$j$位置需要添加括号的数量

因为要找最小的次数，所以给$dp[i][j]$的初始值可以设为字符串的长度（足够大就可以），当$i=j$的时候，至多需要$1$个括号就能匹配了，所以初始值为$1$

如果当前$i$和$j$位置的括号可以匹配，那么$[i,j]$之间需要的括号数和$[i+1,j-1]$的相同，所以$dp[i][j]=dp[i+1][j-1]$

然后查询$[i,j]$之间需要的最少括号数，$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])$

AC代码

/*************************************************************************    > File Name: 15.cpp    > Author: WZY    > School: HPU     > Created Time: 2019年01月21日 15:18:59 ************************************************************************/#include
    
     #define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define pi acos(-1.0)#define INF 0x7f7f7f7fconst double E=exp(1);const int maxn=1e3+10;const int mod=1e9+7;using namespace std;char ch[maxn];// dp[i][j]表示从i到j位置匹配所需要添加的括号数int dp[maxn][maxn];bool check(char a,char b){
    	if((a=='['&&b==']')||(a=='('&&b==')'))		return true;	else		return false;}int main(int argc, char const *argv[]){
    	ios::sync_with_stdio(false);	int t;	cin>>t;	while(t--)	{
    		cin>>ch;		int l=strlen(ch);		for(int i=0;i
     
      =0;i--)		{
    			for(int j=i+1;j