题目链接:传送门
题目大意:中文题，略
题目思路:区间DP
这个题是问需要添加多少个括号使之成为合法括号序列，那么我们可以先求有多少合法的括号匹配，然后用字符串长度减去匹配的括号数就行
状态转移方程主要是对于我们枚举的区间 dp[i][j]，如果 i 和 j 处的括号能够匹配，则dp[i][j]=dp[i+1][j-1]+1;
因为我们是从小到大枚举长度，所以小长度的区间一定是最优的，所以当 i 与 j 匹配时，则是子区间的最优值+1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 100005
#define maxn 1050
typedef pair<int,int> PII;
typedef long long LL; int n,m,cnt,temp,ans;
char str[];
int dp[][];
int main(){
int i,j,group,Case=;
while(scanf("%s",str+)!=EOF){
mst(dp,);
int len=strlen(str+);
for(int p=;p<=len;++p)
for(i=;i<=len;++i){
j=i+p-;if(j>len)break;
if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))dp[i][j]=dp[i+][j-]+;
for(int k=i;k<j;++k){
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]);
}
}
printf("%d\n",len-dp[][len]*);
}
return ;
}