算法竞赛入门经典-(第2版)

内容简介

本书是一本算法竞赛的入门与提高教材，把C/C++语言、算法和解题有机地结合在一起，淡化理论，注重学习方法和实践技巧。全书内容分为12 章，包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、C++与STL入门、数据结构基础、暴力求解法、算法设计、动态规划初步、数学概念与方法、图论模型与算法、专题等内容，覆盖了算法竞赛入门和提高所需的主要知识点，并含有大量例题和习题。书中的代码规范、简洁、易懂，不仅能帮助读者理解算法原理，还能教会读者很多实用的编程技巧；书中包含的各种开发、测试和调试技巧也是传统的语言、算法类书籍中难以见到的。
本书可作为全国青少年信息学奥林匹克联赛（NOIP）复赛教材、全国青少年信息学奥林匹克竞赛（NOI）和ACM大学生程序设计竞赛（ACM/ICPC）的训练资料，也可作为IT工程师与科研人员的参考用书。

目录

第1部分语言篇
第1章程序设计入门... 1
1.1  算术表达式     1
1.2  变量及其输入     3
1.3  顺序结构程序设计     6
1.4  分支结构程序设计     9
1.5  注解与习题     13
1.5.1  C语言、C99、C11及其他     13
1.5.2  数据类型与输入格式     14
1.5.3  习题     15
1.5.4  小结     16
第2章循环结构程序设计... 18
2.1 
for循环     18
2.2 
while循环和do-while循环     22
2.3  循环的代价     25
2.4  算法竞赛中的输入输出框架     27
2.5  注解与习题     34
2.5.1  习题     34
2.5.2  小结     36
第3章数组和字符串... 37
3.1  数组     37
3.2  字符数组     41
3.3  竞赛题目选讲     45
3.4  注解与习题     53
3.4.1  进位制与整数表示     54
3.4.2  思考题     55
3.4.3  黑盒测试和在线评测系统     55
3.4.4  例题一览与习题     56
3.4.5  小结     59
第4章函数和递归... 61
4.1  自定义函数和结构体     61
4.2  函数调用与参数传递     65
4.2.1  形参与实参     65
4.2.2  调用栈     66
4.2.3  用指针作参数     69
4.2.4  初学者易犯的错误     71
4.2.5  数组作为参数和返回值     71
4.2.6  把函数作为函数的参数     73
4.3  递归     74
4.3.1  递归定义     74
4.3.2  递归函数     75
4.3.3  C语言对递归的支持     75
4.3.4  段错误与栈溢出     77
4.4  竞赛题目选讲     79
4.5  注解与习题     92
4.5.1  头文件、副作用及其他     93
4.5.2  例题一览和习题     95
4.5.3  小结     99
第5章  C++与STL入门... 100
5.1  从C到C++  100
5.1.1  C++版框架     101
5.1.2  引用     102
5.1.3  字符串     103
5.1.4  再谈结构体     105
5.1.5  模板     106
5.2  STL初步     108
5.2.1  排序与检索     108
5.2.2 

摘要与插图

第9章动态规划初步
学习目标
 
理解状态和状态转移方程
 
理解子结构和重叠子问题
 
熟练运用递推法和记忆化搜索求解数字三角形问题
 
熟悉DAG上动态规划的常见思路、两种状态定义方法和刷表法
 
掌握记忆化搜索在实现方面的注意事项
 
掌握记忆化搜索和递推中输出方案的方法
 
掌握递推中滚动数组的使用方法
 
熟练解决经典动态规划问题
动态规划的理论性和实践性都比较强，一方面需要理解“状态”、“状态转移”、“子结构”、“重叠子问题”等概念，另一方面又需要根据题目的条件灵活设计算法。可以这样说，对动态规划的掌握情况在很大程度上能直接影响一个选手的分析和建模能力。
9.1 数字三角形
动态规划是一种用途很广的问题求解方法，它本身并不是一个特定的算法，而是一种思想，一种手段。下面通过一个题目阐述动态规划的基本思路和特点。
9.1.1  问题描述与状态定义
数字三角形问题。有一个由非负整数组成的三角形，第一行只有一个数，除了行之外每个数的左下方和右下方各有一个数，如图9-1所示。

（a）数字三角形                          （b）格子编号
图9-1  数字三角形问题
从第一行的数开始，每次可以往左下或右下走一格，直到走到行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？
【分析】
如果熟悉回溯法，可能会立刻发现这是一个动态的决策问题：每次有两种选择——左下或右下。如果用回溯法求出所有可能的路线，就可以从中选出路线。但和往常一样，回溯法的效率太低：一个n层数字三角形的完整路线有2n-1条，当n很大时回溯法的速度将让人无法忍受。
为了得到的算法，需要用抽象的方法思考问题：把当前的位置(i, j)看成一个状态（还记得吗？），然后定义状态(i, j)的指标函数d(i, j)为从格子(i, j)出发时能得到的和（包括格子(i, j)本身的值）。在这个状态定义下，原问题的解是d(1, 1)。
下面看看不同状态之间是如何转移的。从格子(i, j)出发有两种决策。如果往左走，则走到(i+1, j)后需要求“从(i+1, j)出发后能得到的和”这一问题，即d(i+1, j)。类似地，往右走之后需要求解d(i+1, j+1)。由于可以在这两个决策中自由选择，所以应选择d(i+1,j)和d(i+1,j+1)中较大的一个。换句话说，得到了所谓的状态转移方程：

如果往左走，那么情况等于(i, j)格子里的值a(i, j)与“从(i+1, j)出发的总和”之和，此时需注意这里的“”二字。如果连“从(i+1,j)出发走到底部”这部分的和都不是的，加上a(i, j)之后肯定也不是的。这个性质称为子结构（optimal substructure），也可以描述成“全局解包含局部解”。不管怎样，状态和状态转移方程一起完整地描述了具体的算法。
提示9-1：动态规划的核心是状态和状态转移方程。
9.1.2  记忆化搜索与递推
有了状态转移方程之后，应怎样计算呢？
方法1：递归计算。程序如