HDU 3351 Seinfeld(括号匹配)
2024-10-18 22:35:32
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3351
解题报告:输入一个只有'{'跟'}'的字符串,有两种操作,一种是把'{'变成'}',另一种是'}'变成'{',问你要把这个字符串的括号变成合法的最少需要多少次操作。
在刷DP专题,居然有个这个题目,看起来也像是DP,一直在想用DP怎么做,始终没做出来,最后试下直接字符串匹配居然A了。跟普通的字符串匹配的区别就是
在插入'}'这个的时候判断一下栈是不是为空,如果栈为空,则把这个'}'改为'{'再插入,最后判断栈是不是空,如果栈不为空,则剩下的一定都是'{'这个,所以只要把一般的
'{'这个改成'}'这个就可以了,所以还要加上一般的栈长度才是最后答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
#define maxn 2005
char str[maxn];
int dp[maxn][maxn];
int judge(int i,int j)
{
int tot = ;
if(str[i] != '{') tot++;
if(str[j] != '}') tot++;
return tot;
}
deque<char> que;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int kase = ;
while(scanf("%s",str)!=EOF)
{
int len = strlen(str),ans = ;
if(str[] == '-') break;
que.clear();
for(int i = ;i < len;++i)
{
if(str[i] == '{')
que.push_front(str[i]);
else
{
if(que.empty())
{
que.push_front('{');
ans++;
}
else que.pop_front();
}
}
if(!que.empty())
ans += (que.size()/);
printf("%d. %d\n",kase++,ans);
}
return ;
}
/* memset(dp,0,sizeof(dp));
for(int i = len-1;i >= 0;--i)
for(int j = i + 1;j < len;j+=2)
{
dp[i][j] = 0x7fffffff;
if(j == i + 1) dp[i][j] = judge(i,j);
else
{
dp[i][j] = min(dp[i+1][j-1]+judge(i,j),dp[i][j]);
if(j >= 2)
dp[i][j] = min(dp[i][j-2]+judge(j-1,j),dp[i][j]);
if(i+2 < len)
dp[i][j] = min(dp[i+2][j]+judge(i,i+1),dp[i][j]);
}
}
printf("%d. %d\n",kase++,dp[0][len-1]);
}
return 0;
}*/
最新文章
- 创建新用户,连接Oracle数据库
- cordova-screenshot
- 【网站国际化必备】Asp.Net MVC 集成Paypal(贝宝)快速结账 支付接口 ,附源码demo
- Beta项目冲刺 --第一天
- EmguCV 如何从数组中创建出IntPtr
- 【原】关于使用jieba分词+PyInstaller进行打包时出现的一些问题的解决方法
- kettle job通过javascript进行循环控制
- linux邮件服务器postfix配置实例
- Codeforces Beta Round #13 E. Holes 分块暴力
- Delphi 6 Web Services初步评估之二(转)
- 编写jeb插件打印目标方法的交叉引用
- jQuery的入门与简介《思维导图》
- fragment详解(官方文档)
- [每日一题] 11gOCP 1z0-052 :2013-09-15 Enterprise Manager Support Workbench..................B9
- Hadoop 配置文件简介
- HashSet源码分析
- mnist的格式说明,以及在python3.x和python 2.x读取mnist数据集的不同
- HTTPS通信原理
- linux 定期清除日志
- IIS远程发布(Web Deploy)
热门文章
- VS编译器从DLL导出模板类
- tableview中在tableheaderView上放一个视图,第一次进入视图显示不正常,往下拉视图仍然不正常,往上拉视图正常
- SDK
- Apache配置--用户认证(针对目录访问)-update2015-05-02
- Description DisplayName Display的关系
- [Unity] 查找资源
- 使用 trash-cli 逃出 rm 命令误删除重要文件的阴影
- 使用微信JS-SDK调用微信浏览器的接口
- linux下代替system的基于管道的popen和pclose函数
- Linux服务器管理: 系统管理:系统资源查看