第1章 算法概述 1
1.1引言 1
1.1.1算法的描述 1
1.1.2算法的设计 3
1.2算法的复杂性 6
1.2.1时间复杂性 6
1.2.2空间复杂性 9
1.3大学生程序设计竞赛概述 10
1.4程序设计在线测试题库 11
第2章 数据结构和标准模板库 13
2.1栈 13
2.2向量 14
2.3映射 15
2.4列表 17
2.5集合 19
2.6队列 20
2.7优先队列 21
2.8 ZOJ1004-Anagrams by Stack 23
2.9 ZOJ1094-Matrix Chain Multiplication 25
2.10 ZOJ1011-NTA 28
2.11 ZOJ1062-Trees Made to Order 33
2.12 ZOJ1097-Code the Tree 37
2.13 ZOJ1156-Unscrambling Images 40
2.14 ZOJ1167-Trees on the Level 45
2.15 ZOJ1016-Parencodings 47
2.16 ZOJ1944-Tree Recovery 50
2.17 ZOJ2104- Let the Balloon Rise 52
上机练习题 54
第3章 递归与分治策略 56
3.1递归算法 56
3.1.1 Fibonacci数列 57
3.1.2集合的全排列问题 58
3.1.3整数划分问题 59
3.2分治策略 60
3.2.1分治法的基本步骤 60
3.2.2分治法的适用条件 61
3.2.3二分搜索技术 61
3.2.4循环赛日程表 62
3.2.5棋盘覆盖问题 64
3.2.6选择问题 67
3.2.7输油管道问题 69
3.2.8半数集问题 70
3.2.9整数因子分解 72
3.2.10取余运算 73
3.3 Big String 74
上机练习题 76
第4章 动态规划 77
4.1矩阵连乘积问题 78
4.1.1分析最优解的结构 80
4.1.2建立递归关系 81
4.1.3计算最优值 81
4.1.4构造最优解 84
4.2动态规划算法的基本要素 84
4.2.1最优子结构 85
4.2.2重叠子问题 85
4.2.3备忘录方法 86
4.3最长公共子序列 87
4.3.1最长公共子序列的结构 88
4.3.2子问题的递归结构 88
4.3.3计算最优值 89
4.3.4构造最长公共子序列 90
4.4最大子段和 91
4.5 0-1背包问题 93
4.5.1递归关系分析 93
4.5.2算法实现 94
4.6最长单调递增子序列 95
4.7数字三角形问题 96
4.8 ZOJ1013-Great Equipment 98
4.9 ZOJ1027-Human Gene Functions 104
4.10 ZOJ1074-To the Max 107
4.11 ZOJ1093-Monkey and Banana 109
4.12 ZOJ1100-Mondriaan’s Dream 114
4.13 ZOJ1102-Phylogenetic Trees Inherited 118
4.14 ZOJ1107-FatMouse and Cheese 122
4.15 ZOJ1108-FatMouse’s Speed 125
4.16 ZOJ1132-Railroad 129
4.17 ZOJ1147-Formatting Text 134
4.18 ZOJ1149-Dividing 139
4.19 ZOJ1163-The Staircases 143
4.20 ZOJ1183-Scheduling Lectures 145
4.21 ZOJ1196-Fast Food 148
4.22 ZOJ1206-Win the Bonus 152
4.23 ZOJ1227-Free Candies 155
4.24 ZOJ1234-Chopsticks 159
上机练习题 162
第5章 贪心算法 165
5.1活动安排问题 165
5.2贪心算法的理论基础 167
5.2.1贪心选择性质 168
5.2.2最优子结构性质 168
5.2.3贪心算法的求解过程 168
5.3背包问题 169
5.4最优装载问题 172
5.5单源最短路径 173
5.6最小生成树 177
5.6.1最小生成树的性质 177
5.6.2 Prim算法 178
5.6.3 Kruskal算法 180
5.7删数问题 183
5.7.1问题的贪心选择性质 184
5.7.2问题的最优子结构性质 184
5.8多处最优服务次序问题 185
5.8.1问题的贪心选择性质 187
5.8.2问题的最优子结构性质 187
5.9 ZOJ1012-Mainframe 187
5.10 ZOJ1025-Wooden Sticks 192
5.11 ZOJ1029-Moving Tables 194
5.12 ZOJ1076-Gene Assembly 197
5.13 ZOJ1161-Gone Fishing 199
5.14 ZOJ1171-Sorting the Photos 202
5.15 ZOJ2109-FatMouse’Trade 204
上机练习题 206
第6章 回溯算法 207
6.1回溯算法的理论基础 207
6.1.1问题的解空间 207
6.1.2回溯法的基本思想 207
6.1.3子集树与排列树 210
6.2装载问题 211
6.3 0-1背包问题 214
6.4图的m着色问题 216
6.5 n皇后问题 219
6.6旅行商问题 221
6.7流水作业调度问题 223
6.8子集和问题 226
6.9 ZOJ1145-Dreisam Equations 228
6.10 ZOJ1157-A Plug for UNIX 233
6.11 ZOJ1166-Anagram Checker 238
6.12 ZOJ1213-Lumber Cutting 242
上机练习题 246
第7章 分支限界算法 248
7.1分支限界算法的基本理论 248
7.1.1分支限界算法策略 248
7.1.2分支结点的选择 249
7.1.3提高分支限界算法的效率 249
7.1.4限界函数 250
7.2单源最短路径问题 250
7.3装载问题 254
7.4 0-1背包问题 258
7.5旅行商问题 264
7.6 ZOJ1136-Multiple 267
7.7回溯算法与分支限界算法的比较 270
上机练习题 271
第8章 图的搜索算法 272
8.1图的深度优先搜索遍历 272
8.2 ZOJ1002-Fire Net 273
8.3 ZOJ1008-Gnome Tetravex 276
8.4 ZOJ1047-Image Perimeters 280
8.5 ZOJ1084-Channel Allocation 284
8.6 ZOJ1142-Maze 287
8.7 ZOJ1190-Optimal Programs 291
8.8 ZOJ1191-The Die Is Cast 297
8.9 ZOJ1204-Additive Equations 301
8.10 ZOJ1245-Triangles 304
8.11 ZOJ2100-Seeding 307
8.12图的广度优先搜索遍历 309
8.13 ZOJ1055- Oh，Those Achin’Feet 310
8.14 ZOJ1079- Robotic Jigsaw 317
8.15 ZOJ1085-Alien Security 322
8.16 ZOJ1103- Hike on a Graph 325
8.17 ZOJ1148- The Game 329
8.18 ZOJ1217-Eight 332
8.19 ZOJ 1091-Knight Moves 337
上机练习题 342
参考文献 344