|
题目描述
Hecy 又接了个新任务：BE 处理。BE 中有一类被称为 GBE。
以下是 GBE 的定义：
- 空表达式是 GBE
- 如果表达式?
A?是 GBE，则?[A]?与?(A)?都是 GBE - 如果?
A?与?B?都是 GBE，那么?AB?是 GBE
下面给出一个 BE，求至少添加多少字符能使这个 BE 成为 GBE。
输入格式
输入仅一行，为字符串 BE。
输出格式
输出仅一个整数，表示增加的最少字符数。
样例
样例输入
复制[])
样例输出
复制1
数据范围与提示
对于100%的数据，输入的字符串长度小于 100
注：一个简单的区间DP
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,d[105][105];
string s;
bool match(char a,char b){
return ((a=='['&&b==']')||(a=='('&&b==')'));
}
void dp(){
for(int i=0;i<n;i++)
d[i+1][i]=0,d[i][i]=1;
for(int i=n-2;i>=0;i--)
for(int j=i+1;j<n;j++){
d[i][j]=n;
if(match(s[i],s[j])) d[i][j]=min(d[i][j],d[i+1][j-1]);
for(int k=i;k<j;k++)
d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);
}
}
int main(){
cin>>s;
n=s.length();
dp();
printf("%d",d[0][n-1]);
return 0;
}
参考：《算法竞赛入门指南》
|