#include<stdio.h>
#include<string.h>
char _stack[205];
int head = -1;
int rear;
void pop()
{
head--;
}
void push(char ch)
{
_stack[++head] = ch;
}
char top()
{
return _stack[head];
}
int main()
{
int n;
int i;
int j;
int cnt;
int run;
char str[105];
scanf("%d",&n);
while(n--)
{
cnt = 0;
head = -1;
scanf("%s",str);
for(i=0; i<strlen(str); i++)
{
switch(str[i])
{
case '(':
case '[':
push(str[i]);
break;
case ']':
if(top()=='[')
pop();
else if(top()=='(')
{
run = 1;
for(j=0; j<head; j++)
{
if(_stack[j]=='[')
{
pop();
cnt++;
i--;
run = 0;
break;
}
}
if(run)
cnt++;
}
else
cnt++;
break;
case ')':
if(top()=='(')
pop();
else if(top()=='[')
{
run = 1;
for(j=0; j<head; j++)
{
if(_stack[j]=='(')
{
pop();
cnt++;
i--;
run = 0;
break;
}
}
if(run)
cnt++;
}
else
cnt++;
break;
default:
break;
}
}
cnt+=head+1;
printf("%d\n",cnt);
}
}
RT记录一下 标程式DP也帖一下以后看
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=110;
char tab[maxn];
int f[maxn][maxn];
int fun(int i,int j)
{
if(i>j)return 0;
if(f[i][j]>=0)return f[i][j];
if(i==j)return f[i][j]=1;
int va=maxn;
if((tab[i]=='('&&tab[j]==')') || (tab[i]=='['&&tab[j]==']'))
va=fun(i+1,j-1);
for(int mid=i;mid<j;mid++){
va=min(va,fun(i,mid)+fun(mid+1,j));
}
return f[i][j]=va;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
memset(f,-1,sizeof(f));
memset(tab,0,sizeof(tab));
scanf("%s",tab);
cout<<fun(0,strlen(tab)-1)<<endl;
}
}