全新正版 信息学竞赛宝典 动态规划 张新华,胡向荣,伍婉秋 编 人民邮电出版社 计算机与互联网/计算机工具书

章 不下降子序列问题

1.1.不下降子序列 1

1.2.抄近路 6

1.3.宝藏 7

1.4.导弹拦截 8

1.5.和谐俱乐部 9

1.6.滑雪 10

1.7.拓展与练习 12

第2章  背包问题

2.1.简单背包问题 13

2.2.0/1背包问题 15

2.3.0/1背包算法的优化 17

2.4.分组背包问题 18

2.4.1.二维数组动态规划算法 19

2.4.2.一维数组优化算法 20

2.5.拓展与练习 21

第3章  完全背包问题

3.1.完全背包 22

3.2.完全背包算法的优化 23

3.3.拓展与练习  24

第4章  多重背包问题

4.1.多重背包 25

4.2.通天塔 27

4.3.忙碌 28

4.4.拓展与练习 29

第5章  二维费用背包问题

5.1.训练赛 30

5.2.电脑游戏 31

5.3.拓展与练习 32

第6章  区间动态规划

6.1.书架问题1 33

6.2.书架问题2 35

6.3.收购珍珠 37

6.4.双色马 38

6.5.归并石子１ 39

6.6.切割铜棒 44

6.7.邮局问题 45

6.8.乘积 47

6.9.凸多边形三角划分 49

6.10.凸多边形分割 51

6.11.拓展与练习 54

第7章  路径问题

7.1.短路径 55

7.2.少交通费用问题 60

7.3.拓展与练习 62

第8章  资源类动态规划

8.1.机器分配 63

8.2.调度问题

8.3.系统可靠 66

8.4.购物 67

8.5.快餐问题 69

8.6.拓展与练习 71

第9章  动态规划的简单优化

9.1.丝绸之路 72

9.1.1.动态规划算法一 73

9.1.2.动态规划算法二 73

9.1.3.动态规划算法三 74

9.2.双人游戏 75

9.2.1.动态规划算法一 76

9.2.2.动态规划算法二 76

9.3.理想收入问题 77

9.3.1.朴素算法 78

9.3.2.优化算法一 78

9.3.3.优化算法二 79

9.3.4.优化算法三 80

9.3.5.优化算法四 80

9.3.6.贪心算法 81

9.4.唱片录制 82

9.4.1.动态规划算法一 83

9.4.2.动态规划算法二 84

9.4.3.动态规划算法三 85

9.5.相遇问题 86

9.5.1.动态规划算法 87

9.5.2.普通递归算法 89

9.5.3.优化递归算法 91

9.5.4.宽度优先搜索算法 92

9.5.5.动态规划算法的优化 93

9.6.拓展与练习 96

0章  连续子序列问题

10.1.连续子序列和 97

10.2.连续子序列积 98

10.3.k个连续子序列和 99

10.4.拓展与练习 101

1章  子矩阵问题

11.1.二维子矩阵问题 102

11.2.扩展子矩阵问题 104

11.3.子矩阵变形问题 105

11.4.拓展与练习 107

2章  子序列问题

12.1.前缀 108

12.2.zipper 110

12.3.公共子序列 111

12.3.1.动态规划算法一 112

12.3.2.动态规划算法二 115

12.4.确定基因功能 115

12.5.公共上升子序列 118

12.5.1.基本算法 119

12.5.2.优化算法 120

12.6.拓展与练习 122

3章  双重动态规划

13.1.城市交通 123

13.2.复杂的审批 126

13.3.拓展与练习 128

4章  多进程动态规划

14.1.方格取数 129

14.2.三取方格数 132

14.3.拓展与练习 134

5章  树形动态规划

15.1.加分二叉树 135

15.2.宝藏 137

15.3.选课 141

15.4.没有上司的舞会 144

15.5.拓展与练习 146

6章  数位动态规划

16.1.包含417

16.2.幸运数字 152

16.3.拓展与练习 155

7章  状态压缩动态规划

17.1.混乱的队伍 156

17.2.放置猛兽一 158

17.3.放置猛兽二 160

17.4.炮兵阵地 162

17.5.清扫计划 1

17.6.拓展与练习 166

8章  动态规划的高级优化

18.1.单调队列优化 167

18.1.1.子序列和 167

18.1.2.烽火传递 169

18.1.3.多重背包 171

18.1.4.纪念手表 174

18.2.四边形不等式优化 175

18.2.1.归并石子3 175

18.2.2.破坏铁路 178

18.2.3.分段 179

18.3.斜率优化 180

18.4.拓展与练习 184

9章  综合训练

19.1.逢低吸纳 185

19.2.红牌 186

19.3.点菜 187

19.4.选数统计 187

19.5.乌龟棋 188

19.6.守望者的逃离 189

19.7.三角形面积 190

19.8.积木游戏 191

19.9.多米诺骨牌 192

19.10.子树和 193

19.11.访问美术馆 194

19.12.花园 194

19.13.旅行计划 195

19.14.垃圾井 196

19.15.重建道路 197

19.16.迎接仪式 198

19.17.棋盘制作 199

19.18.打砖块 200

19.19.血缘关系 201

19.20.集合方案数 202

19.21.基因序列 203

19.22.基因武器 204

19.23.压路机 204

19.24.旅行商 206

19.25.二叉苹果树 207

19.26.技能树 208

19.27.骑士 209

19.28.猛兽动物园 210

张新华
中学高级教师，信息学竞赛教练。取得浙江大学计算机科学与技术士学、厦门大学软件工程硕士，获得 2009年普通高中信息技术现场优质课比赛全国一等奖。培养的学生多次获得全国青少年奥林匹克联赛一等奖及亚太与太平洋地区信息学奥林匹克竞赛奖牌。著有“信息学竞赛宝典”系列书。开发了三维图形化 C++ 编程工具 Dev-C++ 智能开发平
台和 Python 可视化界面设计软件 Visual Python。
胡向荣
安徽省信息学竞赛教练。获得中国首届网络管理员大赛亚军，安徽省首届计算机技术大赛一等奖，安徽省信息技术优质课评选一等奖。安庆市教育技术专家、信息技术学科骨、教研个人。
伍婉秋
初中信息技术一级教师，广州市白云区永平片初二信息技术教研组组长；参与全国教育科学“十三五”规划课题“三维图形化智能编程系统在中小学编程教育中的构建和应用”；曾获广州市中学信息技术教师教学能力比赛二等奖、白云区一等奖。

● 难得一见的动态规划算法专项训练书
● 直接以各类竞赛真题入手
● 配有 PPT+ 源码 + 讲解视频
● 提供对应在线题库

1.代码精炼、语言简练、内容全面、擅长将复杂的算法思想用浅显的图文形式描述。
2.讲解细致，关键代码有注释，有行号便于教师讲解，采用专业等宽编程字体，对初学者易犯的错误有提醒。
3.注重思维训练，一题多解，培养用数学思维解题。
4.全套经过多次校验过的精练码参及测试数据。
5.配有视频讲解，完整展示解题过程。
6.作者在算法竞赛领域有着多年的积累。