题目链接: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;
}*/

最新文章

  1. 创建新用户,连接Oracle数据库
  2. cordova-screenshot
  3. 【网站国际化必备】Asp.Net MVC 集成Paypal(贝宝)快速结账 支付接口 ,附源码demo
  4. Beta项目冲刺 --第一天
  5. EmguCV 如何从数组中创建出IntPtr
  6. 【原】关于使用jieba分词+PyInstaller进行打包时出现的一些问题的解决方法
  7. kettle job通过javascript进行循环控制
  8. linux邮件服务器postfix配置实例
  9. Codeforces Beta Round #13 E. Holes 分块暴力
  10. Delphi 6 Web Services初步评估之二(转)
  11. 编写jeb插件打印目标方法的交叉引用
  12. jQuery的入门与简介《思维导图》
  13. fragment详解(官方文档)
  14. [每日一题] 11gOCP 1z0-052 :2013-09-15 Enterprise Manager Support Workbench..................B9
  15. Hadoop 配置文件简介
  16. HashSet源码分析
  17. mnist的格式说明,以及在python3.x和python 2.x读取mnist数据集的不同
  18. HTTPS通信原理
  19. linux 定期清除日志
  20. IIS远程发布(Web Deploy)

热门文章

  1. VS编译器从DLL导出模板类
  2. tableview中在tableheaderView上放一个视图,第一次进入视图显示不正常,往下拉视图仍然不正常,往上拉视图正常
  3. SDK
  4. Apache配置--用户认证(针对目录访问)-update2015-05-02
  5. Description DisplayName Display的关系
  6. [Unity] 查找资源
  7. 使用 trash-cli 逃出 rm 命令误删除重要文件的阴影
  8. 使用微信JS-SDK调用微信浏览器的接口
  9. linux下代替system的基于管道的popen和pclose函数
  10. Linux服务器管理: 系统管理:系统资源查看