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

动态规划 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-02-16
  • 蒲县工商质监局非公党委举办2018元旦文艺会 2019-02-16
  • 人民网评:建设数字中国时不我待 2019-02-16
  • 618史上最壕“买家”现身 Google以 5.5亿美元投资京东 2019-02-15
  • 雍正官窑:朕就是这样的品味(图) 2019-02-15
  • 西安司法考试将试点机考 2019-02-15
  • 人民日报新媒体矩阵聚焦十九大 融媒报道"给你好看" 2019-02-14
  • 社会主义是过渡阶段,最终实现共产主义才是其目的。社会主义是在消灭私有制,建立公有制直至无私,实现共产主义。 2019-02-14
  • 四轮电动车销售火爆存安全隐患 专家:需建国家标准 2019-02-14
  • 看懂汽车三元催化器工作原理后还能当金子卖?难为非洲兄弟了! 2019-02-14
  • 周杰伦昆凌为儿子庆生 小小周帅气入镜 2019-02-13
  • 都以为机器人普及了,一切都不是问题了?机器人不需要不断升级?机器人生产啥?不需要人设计? 2019-02-13
  • 价值-热门标签-华商生活 2019-02-13
  • 上合组织引领发展 吉中合作稳步前行——访吉尔吉斯斯坦总统热恩别科夫 2019-02-13
  • 互联网金融协会提示:防范变相“现金贷”业务风险 2019-02-12
  • 297| 429| 737| 160| 47| 324| 331| 298| 951| 475|