递归与回溯

递归与回溯

[算法分析]
为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这
种用自已来定义自己的方法，称为递归定义。例如：定义函数f(n)为：
/n*f(n－1) (n>0)
f(n)= |
/ 1(n=0)
则当0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。
由上例我们可看出，递归定义有两个要素：
（1）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。
如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。
（2）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。
如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。

递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步没其结果仍维持原问题的关系, 则采用递归算法编程比较合适.

递归按其调用方式分为: 1. 直接递归, 递归过程P直接自己调用自己; 2. 间接递归, 即P包含另一过程D, 而D又调用P.

递归算法适用的一般场合为:
1. 数据的定义形式按递归定义.
如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
对应的递归程序为:
Function fib(n : integer) : integer;
Begin
if n = 0 then fib := 1 { 递归边界 }
else if n = 1 then fib := 2
else fib := fib(n-2) + fib(n-1) { 递归 }
End;
这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.
2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.
3. 问题解法按递归算法实现. 例如回溯法等.

从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "
的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作
" 回溯法 ".

[参考程序]
下面给出用回溯法求所有路径的算法框架. 注释已经写得非常清楚, 请读者仔细理解.
Const maxdepth = ????;
Type statetype = ??????; { 状态类型定义 }
operatertype = ??????; { 算符类型定义 }
node = Record { 结点类型 }
state : statetype; { 状态域 }
operater :operatertype { 算符域 }
End;
{ 注: 结点的数据类型可以根据试题需要简化 }
Var
stack : Array [1..maxdepth] of node; { 存当前路径 }
total : integer; { 路径数 }
Procedure make(l : integer);
Var i : integer;
Begin
if stack[L-1]是目标结点 then
Begin
total := total+1; { 路径数+1 }
打印当前路径[1..L-1];
Exit
End;
for i := 1 to 解答树次数 do
Begin
生成 stack[l].operater;
stack[l].operater 作用于 stack[l-1].state, 产生新状态 stack[l].state;
if stack[l].state 满足约束条件 then make(k+1);
{ 若不满足约束条件, 则通过for循环换一个算符扩展 }
{ 递归返回该处时, 系统自动恢复调用前的栈指针和算符, 再通过for循环换一个算符扩展 }
{ 注: 若在扩展stack[l].state时曾使用过全局变量, 则应插入若干语句, 恢复全局变量在
stack[l-1].state时的值. }
End;
{ 再无算符可用, 回溯 }
End;
Begin
total := 0; { 路径数初始化为0 }
初始化处理;
make(l);
打印路径数total
End.

[例子]求N个数的全排列。
［分析］求N个数的全排列，可以看成把N个不同的球放入N个不同的盒子中，每个盒子中只能有一
个球。解法与八皇后问题相似。
［参考过程］
procedure try(I:integer);
var j:integer;
begin
for j:=1 to n do
if a[j]=0 then
begin
x[I]:=j;
a[j]:=1;
if I<n then try(I+1)
else print;
a[j]=0;
end;
end;

[习题] 用递归完成：
1、如下图，打印0－N的所有路径(0=〈N〈=9)：
1―> 3―> 5―> 7―> 9
^ ^ ^ ^ ^
| | | | |
0―> 2―> 4―> 6―> 8
(说明：图中须加上0－>3，2－>5，4－>7，6－>9的连线)
2、快速排序。
3、打印杨辉三角。
最后, 给出一道经典的使用回溯算法解决的问题, 留给读者思考.
题目描述:
对于任意一个m*n的矩阵, 求L形骨牌覆盖后所剩方格数最少的一个方案.

素数环

---

〖问题描述〗
把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。

〖问题分析〗(聿怀中学 吴轲)
非常明显，这是一道回溯的题目。从1开始，每个空位有20（19）种可能，只要填进去的数合法：
与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。

〖算法流程〗
1、数据初始化；
2、递归填数：
判断第J种可能是否合法；
A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；
B、如果不合法：选择下一种可能；

〖参考程序〗ssh.pas

八皇后问题

---

〖问题描述〗
在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。

〖问题分析〗(聿怀中学 吕思博)
这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：
1、冲突。包括行、列、两条对角线：
（1）列：规定每一列放一个皇后，不会造成列上的冲突；
（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；
（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
2、数据结构。
（1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8
（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8
（3）对角线冲突标记数组C、D。
C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7
D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16

〖算法流程〗
１、数据初始化。
２、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）:
如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；
如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。
３、当n>8时，便一一打印出结果。

〖优点〗逐一测试标准答案，不会有漏网之鱼。

〖参考程序〗queen.pas

2的幂次方

---

〖问题描述〗
任何一个正整数都可以用2的幂次方表示.
例如:137=2^7+2^3+2^0
同时约定次方用括号来表示,即a^b可表示为a(b)
由此可知,137可表示为:2(7)+2(3)+2(0)
进一步:7=2^2+2+2^0 (2^1用2表示)
3=2+2^0
所以最后137可表示为:2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如:1315=2^10+2^8+2^5+2+1
所以1315最后可表示为:2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
输入:正整数(n<=20000)
输出:符合约定的n的0,2表示(在表示中不能有空格)

〖问题分析〗

树形结构——二叉树

相关知识： 一维数组 | 多维数组 | 栈 | 队列 | 串

一、树的基本术语
　　　　　　　
　　1.树的度——也即是宽度，以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;
　　2.树的深度——以组成该树各结点的最大层次，如上图，其深度为4；
　　3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；
　　4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
二、树的表示
　　树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
　　　　(A(B(E(K,L),F),C(G),D(H(M),I,J)))
三、二叉树
　　1.二叉树的基本形态：
　　二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
　　　　　
　　(1)空二叉树——(a)；
　　(2)只有一个根结点的二叉树——(b)；
　　(3)右子树为空的二叉树——(c)；
　　(4)左子树为空的二叉树——(d)；
　　(5)完全二叉树——(e)

　　2.两个重要的概念：
　　(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
　　(2)满二叉树——除了叶结点外，每一个结点都有左右子女的二叉树。
　　如下图：
　　　　　　　　　　　　
　　　

　　3.二叉树的性质
　　 (1)在二叉树中，第i层的结点总数不超过2^(i-1)；
　　 (2)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
　　 (3)有N个结点的完全二叉树各结点如果用顺序方式表示，则结点之间有如下关系：

　　　　·如果I<>1，则其父结点的编号为I/2；
　　　　·如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
　　　　·如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
　　4.二叉树的存储结构：
　　　(1)顺序存储方式
　　　　　　　　
　　　(2)链表存储方式，如：
　　　　　数组下标：　　　　1　2　3　4　5　6　7　8
　　　　　数组D：　 　　　　A　B　C　D　E　F　G　H
　　　　　左指针数组L：　　 2　4　6　0　7　0　0　0
　　　　　右指针数组R：　　 3　5　0　0　0　8　0　0
　　5.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。
　　　　　
　　6.二叉树的遍历运算（递归定义）
　　　(1)先序遍历
　　　　　　访问根；按先序遍历左子树；按先序遍历右子树
　　　(2)中序遍历
　　　　　　按中序遍历左子树；访问根；按中序遍历右子树
　　　(3)后序遍历
　　　　　　按后序遍历左子树；按后序遍历右子树；访问根

四、例：
　　1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。(tree1.pas)
　　2.用链表存储方式建立一棵如图三、4所示的二叉树，并对其进行先序遍历。(tree2.pas)
　　3.给出一组数据：R={10.18,3,8,12,2,7,3}，试编程序，先构造一棵二叉树，然后以中序遍历访问所得到的二叉树，并输出遍历结果。(tree3.pas)
　　4.给出八枚金币a,b,c,d,e,f,g,h，编程以称最少的次数，判定它们蹭是否有假币，如果有，请找出这枚假币，并判定这枚假币是重了还是轻了。
　　　　　

分支限界

相关知识： 深度优先 | 广度优先:三角形 | 剪枝搜索| 递归与回溯 | 素数环 | 八皇后问题 | 跳马问题 | 实例：2的幂次方

一、分支限界法：
分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

二、分支限界法的基本思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有 子集树和 排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

三、选择下一扩展结点的不同方式：
从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种方式：
1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。
2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

四、习题：
1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30

2、单源最短路径：求从起点到终点的最短路径。

3、装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi且
。要求确定是否有一个合理的装载方案可将这n个集装箱装上这
2艘轮船。如果有，找出一种装载方案。

4、布线问题：印刷电路板将布线区域划分成n X m个方格如图a所示。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图b所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。

一个布线的例子：图中包含障碍。起始点为a，目标点为b。

动态规划

相关知识： 动态规划 | 最短路径 | 复制书稿 | 车队过桥 | 石子归并

一、动态规划的基本思想：
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

二、设计动态规划法的步骤：
1、找出最优解的性质，并刻画其结构特征；
2、递归地定义最优值（写出动态规划方程）；
3、以自底向上的方式计算出最优值；
4、根据计算最优值时得到的信息，构造一个最优解。
步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。

三、动态规划问题的特征：
动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。
1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

四、习题：
1、防卫导弹：
问题描述：一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：
1、它是该次测试中第一个被防卫导弹截击的导弹；
2、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。
输入格式：从当前目录下的文本文件"CATCHER.DAT"读入数据 。该文 件的第一行是一个整数N（0〈=N〈=4000），表示本次测试中，发射的进攻导弹数，以下N行每行各有一个整数hi（0〈=hi〈=32767），表示第i个进攻导弹的高度。文件中各行的行首、行末无多余空格，输入文件中给出的导弹是按发射顺序排列的。
输出格式：答案输出到当前目录下的文本文件"CATCHER.OUT"中，该文件第一行是一个整数max，表示最多能截击的进攻导弹数，以下的max行每行各有一个整数，表示各个被截击的进攻导弹的编号（按被截击的先后顺序排列）。输出的答案可能不唯一，只要输出其中任一解即可。
输入输出举例：

输入文件：CATCHER.DAT 3 25 36 23

输出文件：CATCHER.OUT 2 1 3

2、轮船(Ships)
描述
有一个国家被一条何划分为南北两部分，在南岸和北岸总共有N个城镇，每一城镇在对岸都有唯一的友好城镇。任何两个城镇都没有相同的友好城镇。每一对友好城镇都希望有一条航线来往。于是他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线交叉（如果两条航线交叉，将有很大机会撞船）。
你的任务是缟写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使到没有出现交叉的航线最多。
输入数据
输入文件（ship.in）包括了若干组数据，每组数据格式如下：
第一行两个由空格分隔的整数x，y，10〈=x〈=6000，10〈=y〈=100。x 表示河的长度而y表示宽。第二行是一个整数N(1<=N<=5000)，表示分布在河两岸的城镇对数。接下来的N行每行有两个由空格分隔的正数C，D（C、D〈=x〉，描述每一对友好城镇沿着河岸与西边境线的距离，C表示北岸城镇的距离而D表示南岸城镇的距离。在河的同一边，任何两个城镇的位置都是不同的。整个输入文件以由空格分隔的两个0结束。
输出数据
输出文件(ship.ou)要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线数目。
示例

Ship.in 30 4 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 0 0	Ship.out 4

动态规划在信息学奥林匹克竞赛中的应用

一.动态规划含义:
在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都要做出决策,从而使整个过程达到最好的活动效果.因此,各个阶段决策确定后,组成一个决策序列,因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程,就称为多阶段决策过程,这种问题称为多阶段决策问题.
在多阶段决策问题中,各个阶段采取的决策,一般来说是和时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有"动态"的含义,我们称这种解决多阶段决策最优化的过程为动态规划.

二.动态规划特征
动态规划的显著特征是:无后效性,有边界条件,且一般划分为很明显的阶段.
动态规划一般还存在一条或多条状态转移方程.

三.例题
1. Catcher防卫导弹 (GDOI'98)
题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列
这道题目一开始我使用回溯算法,大概可以拿到1/3的分吧,后来发现这其实是动态规划算法中最基础的题目,用一个二维数组C[1..Max,1..2]来建立动态规划状态转移方程(注:C[1..Max,1]表示当前状态最多可击落的导弹数,C[1..Max,2]表示当前状态的前继标志):Ci=Max{C[j]+1,(j=i+1..n)},然后程序也就不难实现了.
示范程序:

program catcher_hh;
var
f:text;
i,j,k,max,n,num:integer;
a:array [1..4000] of integer; {导弹高度数组}
c:array [1..4000,1..2] of integer; {动态规划数组}
procedure readfile;
begin
assign(f,'catcher.dat'); reset(f);
readln(f,num);
for i:=1 to num do
readln(f,a[i]);
end;
procedure work;
begin
fillchar(c,sizeof(c),0); c[num,1]:=1; {清空数组,赋初值}
{开始进行动态规划}
for i:=num-1 downto 1 do
begin
n:=0; max:=1;
for j:=i+1 to num do
if (a[i]>a[j]) and (max<1+c[j,1])
then begin n:=j; max:=1+c[j,1]; end;
c[i,1]:=max; c[i,2]:=n;
end;
writeln; writeln('Max : ',max); {打印最大值}
max:=0; n:=0;
for i:=1 to num do
if c[i,1]>max then begin max:=c[i,1]; n:=i; end;
{返回寻找路径}
repeat
writeln(n,' '); n:=c[n,2];
until n=0;
end;
begin
readfile; work;
end.

2. Perform巡回演出 (GDKOI'2000)
题目描述:
Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).
由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.
输入:
输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去.
每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.
输出:
对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.
样例输入:
3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0
样例输出:
460
0
初看这道题,很容易便可以想到动态规划,因为第x天在第y个地方的最优值只与第x-1天有关,符合动态规划的无后效性原则,即只与上一个状态相关联,而某一天x航班价格不难求出S=C[(x-1) mod m +1].我们用天数和地点来规划用一个数组A[1..1000,1..10]来存储,A[i,j]表示第i天到达第j个城市的最优值,C[i,j,l]表示i城市与j城市间第l天航班价格,则A[i,j]=Min{A[i-1,l]+C[l,j,i] (l=1..n且C[l,j,i]<>0)},动态规划方程一出,尽可以放怀大笑了.

示范程序:
program perform_hh;
var
f,fout:text;
p,l,i,j,n,k:integer;
a:array [1..1000,1..10] of integer; {动态规划数组}
c:array [1..10,1..10] of record {航班价格数组}
num:integer;
t:array [1..30] of integer;
end;
e:array [1..1000] of integer;
procedure work;
begin
{人工赋第一天各城市最优值}
for i:=1 to n do
begin
if c[1,i].t[1]<>0
then a[1,i]:=c[1,i].t[1];
end;
for i:=2 to k do
begin
for j:=1 to n do
begin
for l:=1 to n do
begin
if (j<>l)
and (c[l,j].t[(i-1) mod c[l,j].num+1]<>0) {判断存在航班}
and ((a[i,j]=0) or (a[i-1,l]+c[l,j].t[(i-1) mod c[l,j].num+1]<a[i,j])) {判断比当前解优}
then a[i,j]:=a[i-1,l]+c[l,j].t[(i-1) mod c[l,j].num+1]; {赋值}
end;
end;
end;
e[p]:=a[k,n]; {第p个场景的最优值}
end;
procedure readfile; {读文件}
begin
assign(f,'PERFORM.DAT'); reset(f);
assign(fout,'PERFORM.OUT'); rewrite(fout);
readln(f,n,k); p:=0;
while (n<>0) and (k<>0) do
begin
p:=p+1;
fillchar(c,sizeof(c),0);
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
for j:=1 to i-1 do
begin
read(f,c[i,j].num);
for l:=1 to c[i,j].num do
read(f,c[i,j].t[l]);
end;
for j:=i+1 to n do
begin
read(f,c[i,j].num);
for l:=1 to c[i,j].num do
read(f,c[i,j].t[l]);
end;
end;
work;
readln(f,n,k);
end;
{输出各个场景的解}
for i:=1 to p-1 do
writeln(fout,e[i]);
write(fout,e[p]);
close(f);
close(fout);
end;
begin
readfile;
end.

四.小结
动态规划与穷举法相比,大大减少了计算量,丰富了计算结果,不仅求出了当前状态到目标状态的最优值,而且同时求出了到中间状态的最优值,这对于很多实际问题来说是很有用的.这几年,动态规划已在各省市信息学奥林匹克竞赛中占据相当重要的地位,每年省赛8道题目中一般有2~3道题目属于动态规划,动态规划相比一般穷举也存在一定缺点:空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最佳方法!

五.课后题目
1. m个人抄n本书,每本书页数已知,每个人(第一个人除外)都必须从上一个人抄的最后一本书的下一本抄起(书必须整本整本的抄),求一种分配方法,使抄书页数最多的人抄书页数尽可能少. (GDOI''99 Books).
2. 有一字符串有多种编码方式可供人选择，将这个字符串进行编码，使求得得编码长度最短。　（GDKOI'2000 Compress)
3. Canada境内有自西向东的一系列城市：Halifax,Hamilton,Montelia,Vancouver...，各个城市之间可能有航班相连，也可能没有，现要求从最西的城市出发，自西向东到达最东的城市，再返回最西的城市，除最西城市外，其他每个城市只能访问一次，求最多能访问多少个城市．

动态规划（一）

最短路径

〖题目描述〗
有如下有向图，边IJ上的数字为从点I走到点J的代价。求从点A1到点E1之间的最短路径。

〖题目描述〗
假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，…PM）。任务是将这M本书分给K个抄写员（K〈=M〉，每本书只能分配给一个抄写员进行复制，而每个抄写员所分配到的书必须是连续顺序的。
意思是说，存在一个连续升序数列 0 = bo < b1 < b2 < … < bk-1 < bk = m，这样，第I号抄写员得到的书稿是从bi-1+1到第bi本书。复制工作是同时开始进行的，并且每个抄写员复制的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小（如存在多个最优方案，只输出其中一种）。
(GDOI''99 Books).

〖输入格式〗
第一行两个数m,k:表示书本数目与人数;第二行m个由空格分隔的整数,m本书每本的页数.

〖输出格式〗
共k行。每行两个整数：第I行表示第I抄写员抄的书本编号起止。

〖输入输出样例〗

输入样例	输出样例
9 3 1 2 3 4 5 6 7 8 9	1 5 6 7 8 9

Book.pas

过桥问题

---

〖题目描述〗
GDOI工作组遇到了一个运输货物的问题。现在有N辆车要按顺序通过一个单向的小桥，由于小桥太窄，不能有两辆车并排通过，所以在桥上不能超车。另外，由于小桥建造的时间已经很久，所以小桥只能承受有限的重量，记为Max（吨）。所以，车辆在过桥的时候必须要有管理员控制，将这N辆车按初始顺序分组，每次让一个组过桥，并且只有在一个组中所有的车辆全部过桥以后才让下一组车辆上桥。现在，每辆车的重量和最在速度是已知的，而每组车的过桥时间由该组中速度最慢的那辆车决定。
现在请你编一个程序，将这N辆车分组，使得全部车辆通过小桥的时间最短。

输入格式：
数据存放在当前目录下的文本文件“bridge.in”中。
文件的第一行有三个数，分别为Max（吨），Len（桥的长度，单位：Km），N（三个数之间用一个或多个空格分开）。
接下来有N行，每行两个数，第i行的两个数分别表示第i辆车的重量（吨）和最大速度（m/s）。
注意：所有的输入都为整数，并且任何一辆车的重量都不会超过Max。

输出格式：
答案输出到当前目录下的文本文件“bridge.out”中。
文件只有一行，输出全部车辆通过小桥的最短时间（s），精确到小数点后一位。

输入输出样例：

bridge.in	bridge.out
100 5 10 40 25 50 20 70 10 12 50 9 70 49 30 38 25 27 50 19 70	75.0

Bridge.pas

石子归并

〖题目描述〗
在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20).
(!)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小;
(2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最大;

输入数据:
第一行为石子堆数N;
第二行为每堆的石子数,每两个数之间用一个空格分隔.

输出数据:
从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示.

输入输出范例:
输入:
4
4 5 9 4
输出:
-4 5 9 -4
-8 -5 9
-13 -9
22

4 -5 -9 4
4 -14 -4
-4 -18
22

Stone.pas