题目描述
Hecy 又接了个新任务:BE 处理。BE 中有一类被称为 GBE。
以下是 GBE 的定义:
- 空表达式是 GBE
- 如果表达式 A 是 GBE,则 [A] 与 (A) 都是 GBE
- 如果 A 与 B 都是 GBE,那么 AB 是 GBE
下面给出一个 BE,求至少添加多少字符能使这个 BE 成为 GBE。
输入格式
输入仅一行,为字符串 BE。
输出格式
输出仅一个整数,表示增加的最少字符数。
样例
输入
[])
输出
1
数据范围与提示
对于 \(100\%\) 的数据,输入的字符串长度小于 100。
简单的区间DP
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int f[maxn][maxn];
char s[maxn];
int n;
inline bool isd(int l,int r)
{
return (s[l]=='('&&s[r]==')') || (s[l]=='['&&s[r]==']');
}
inline bool isl(int p)
{
return s[p]=='('||s[p]=='[';
}
inline bool isr(int p)
{
return s[p]==')'||s[p]==']';
}
int main()
{
scanf("%s",s+1);
int n=strlen(s+1);
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;++i)f[i][i]=1;
for(int lg=1;lg<n;++lg)
for(int l=1;l<n;++l)
{
int r=l+lg;
if(r>n)break;
if(isd(l,r))f[l][r]=r-l==1?0:f[l+1][r-1];
else
{
if(isl(l))f[l][r]=min(f[l][r],f[l+1][r]+1);
if(isr(r))f[l][r]=min(f[l][r],f[l][r-1]+1);
}
for(int m=l;m<r;++m)
f[l][r]=min(f[l][r],f[l][m]+f[m+1][r]);
}
cout<<f[1][n]<<endl;
return 0;
}
原文地址:http://www.cnblogs.com/gryzy/p/16885554.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性