现在的位置: 首页 > 综合 > 正文

动态规划 Brackets Sequence poj 1141

2018年05月02日 ⁄ 综合 ⁄ 共 2219字 ⁄ 字号 评论关闭

秒速赛车公式 www.l19l7.cn 题目连接://poj.org/problem?id=1141

题目大意:给出一串括号序列(只包含小括号和中括号),求包含次子序列的长度最小的regular brackets sequence。其中regular brackets sequence定义如下:

1.空序列是一个regular brackets sequence;

2.如果s是一个regular brackets sequence,那么[s]也是一个regular brackets sequence,(s)也是一个regular brackets sequence。

3.如果A、B都是regular brackets sequence,那么AB也是一个regular brackets sequence。

例如:()、[]、([])、([])()[()]都是regular brackets sequence

而[[[、(((、([)]则都不是regular brackets sequence

其中一([)]为例,包含它最小的regular brackets sequence有两个:()[()]、([])[],只需输出一个就行。

代码:

  1. #include?<iostream>??
  2. #include?<cstdio>??
  3. #include?<cstring>??
  4. ??
  5. using?namespace?std;??
  6. ??
  7. char?str[105];??
  8. int?dp[101][101];//i到j之间加成为regular?brackets?sequence需要加入的最少字符数??
  9. int?tag[101][101];//用来做标记?记录最少字符时的是那种情况??
  10. int?len;??
  11. ??
  12. void?print(int?s,int?e)??
  13. {??
  14. ????if?(s>e)return;??
  15. ????if?(s==e)??
  16. ????{??
  17. ????????if?(str[s]=='('?||?str[s]==')')??
  18. ????????{??
  19. ????????????printf("()");??
  20. ????????}??
  21. ????????else??
  22. ????????{??
  23. ????????????printf("[]");??
  24. ????????}??
  25. ????????return?;??
  26. ????}??
  27. ????if?(tag[s][e]==-1)??
  28. ????{??
  29. ????????printf("%c",str[s]);??
  30. ????????print(s+1,e-1);??
  31. ????????printf("%c",str[e]);??
  32. ????}??
  33. ????else??
  34. ????{??
  35. ????????print(s,tag[s][e]);??
  36. ????????print(tag[s][e]+1,e);??
  37. ????}??
  38. }??
  39. ??
  40. int?main()??
  41. {??
  42. ????while?(gets(str))??
  43. ????{??
  44. ????????len?=?strlen(str);??
  45. ????????for?(int?i=0;i<len;i++)??
  46. ????????{??
  47. ????????????dp[i][i]=1;//初始??
  48. ????????????dp[i+1][i]=0;//下面在进行DP时,i=j+1时,i=i+1、j=j-1会造成i=j+1??
  49. ????????}??
  50. ????????for?(int?st=1;st<len;st++)??
  51. ????????{??
  52. ????????????for?(int?i=0;i+st<len;i++)??
  53. ????????????{??
  54. ????????????????int?j=i+st;??
  55. ????????????????int?temp=9999999;??
  56. ????????????????if?((str[i]=='('?&&?str[j]==')')||(str[i]=='['?&&?str[j]==']'))??
  57. ????????????????{??
  58. ????????????????????temp=dp[i+1][j-1];//第一种情况(s)或[s]??
  59. ????????????????}??
  60. ????????????????tag[i][j]=-1;??
  61. ????????????????for?(int?k=i;k<j;k++)//第二种情况,枚举i到j之间的k?即AB??
  62. ????????????????{??
  63. ????????????????????int?res=dp[i][k]+dp[k+1][j];??
  64. ????????????????????if?(res<temp)??
  65. ????????????????????{??
  66. ????????????????????????temp=res;??
  67. ????????????????????????tag[i][j]=k;??
  68. ????????????????????}??
  69. ????????????????}??
  70. ????????????????dp[i][j]=temp;??
  71. ????????????}??
  72. ????????}??
  73. ????????print(0,len-1);//根据标记情况进行回溯??
  74. ????????printf("\n");??
  75. ????}??
  76. ????return?0;??
  77. } ?

抱歉!评论已关闭.

  • 倒着走能治腰颈椎痛?假的! 2019-04-19
  • 长效机制加速推进 楼市下半年或持续降温 2019-04-19
  • 树立文化自信 创新节庆模式 2019-04-19
  • 朝韩将军级会谈时隔11年后在板门店重启 2019-04-19
  • 经济日报多媒体数字报刊 2019-04-18
  • 搞好公有制就是好,故得出结论:计划经济好。 2019-04-18
  • 云南理发店老板涉嫌杀害女演员因办卡纠纷起杀心 2019-04-18
  • 南海网-海南新闻网-权威媒体 海南门户 2019-04-17
  • 海底捞回应侵犯音乐人林海著作权:已停止播放 2019-04-17
  • 自然型社会和规则性社会,是会随着科技的改变而发生改变的,当然只有规矩也就是制度才能规范人的行为,所以国家是不会灭亡的,但国家的形式是会发生改变的。 2019-04-17
  • 惊艳!上外学子英译60首热门中文歌  让世界倾听中国 2019-04-16
  • 西安,给盲人朋友留一条路吧…无障碍设施盲道-编辑整合 2019-04-16
  • 的确如此。报刊亭取消的确是短视行为。把报刊亭设计的现代化一些,与城市绿化衔接起来,相得益彰,成为文化一景多好。 2019-04-16
  • 让更多企业和劳动者尝到协商的“甜头” 2019-04-16
  • 2014金家岭财富论坛嘉宾云集(二) 2019-04-15
  • 124| 620| 656| 80| 244| 737| 200| 771| 648| 268|