已知字母A,B和一组字母变换规则(至多100个规则): A1->B1 A2->B2 规则的含义为:如果A=Ak，可以通过一次变换为Bk（1≤k ≤ 规则数） 求从A到B最少需要几次变换。
【输入文件】letter.in
第一行为两个字母，分别是初始字母和变换目标字母。 以下k行为变换规则（1 ≤ k ≤ 100），都是大写字母，两个字母间以空格间隔，直到文件结束。
【输出文件】letter.out
最小的变换次数。如果无法变换，则输入”No Answer!”
【样例数据】
【输入】letter.in
A Z
A E
E F
F T
T Z
A C
C Z
【输出】letter.out
2
【参考程序查看】
在一个地图上有n(n≤20)个地窖,每个地窖中埋有一定数量的地雷,给出地窖之间的联系路径。当地窖极其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径)，挖雷的过程中允许某人重复经过地窖。当无连接时，挖地雷工作结束。请编程设计一个挖地雷的方案，使某人能挖到的最多的地雷。
【输入文件】miner.in
n(地窖个数)
v1 v2 v3 ... vn (每个地窖的地雷数)
a(1,2) ... a(1,n)
a(2,3) ... a(2,n)
.
.
.
a(n-1,n)
(表示地窖之间连接路径，其中a(i,j)表示地窖i,j之间是否有通路，若有通路，则a(i,j)=1，若无通路，则a(i,j)=0）
【输出文件】miner.out
R1-R2-...-Rk(挖地雷的顺序)
Max(挖的地雷总数)
【样例数据】
【输入】miner.in
6
2 10 20 8 5 7
0 0 0 1 1
1 0 0 0
0 0 0
0 1
1
【输出】miner.out
2-3
30
【参考程序查看】
乌托邦有n个城市，某些城市之间有公路连接。任意两个城市都可以通过公路直接或间接到达，并且任意两个城市之间有且仅有一条路径。
每条公路都有自己的长度，这些长度都是已经测量好的。小修想从一个城市出发开车到另一个城市，并且她希望经过的公路总长度最长。请问她应该选择哪两个城市？这个最长的长度是多少？
【输入文件】wutuo.in
第一行一个整数n(表示n个城市，n≤100)，以下n-1行每行三个整数a,b,c。表示城市之间有公路连接，并且公路的长度是c(c≤10000)。
【输出文件】wutuo.out
仅一个数，即最长长度
【样例数据】
【输入】wutuo.in
5
1 2 2
2 3 1
2 4 3
1 5 4
【输出】wutuo.out
9
【参考程序查看】
住在乌托邦首都（编号为1）的天凯，开始对首都的交通情况感到不满，因为，他发现首都到某些城市，即使他选择最短的路径，距离也非常远。因此他想让你求一下交通中心城市是哪座城市（也有可能就是首都）。
为了说明交通中心城市的概念，先定义G为距离城市i最远的城市（到城市i的最短路径长度最长的城市）到城市i的距离。那么交通中心城市都是G最小的城市，如果有几个城市的G一样小，则是编号最小的那个。
【输入文件】capital.in
第一行两个整数n,m(n≤100)。下面m行，每行三个整数，第i+1行的整数表示第i条高速公路连接的两个城市编号和长度（0<L<10000）。
【输出文件】capital.out
仅一个数，表示交通中心城市的编号
【样例数据】
【输入】capital.in
5 5
1 2 1
1 5 6
2 3 2
2 4 1
4 5 2
【输出】capital.out
2
【参考程序查看】
[ 本帖最后由 kon3155 于 2009-2-25 12:53 编辑 ]
【最短路径问题】
下图给出了一张地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度，求从A地到E地的最短路径。
http://www.zjtg.cn/itjs/suanfa/images/7_1.gif
【分析】本题可以利用深度搜索法求解，伪代码如下：
var
s:未访问的城市集合;
dist:存储任意两个城市间的距离数组; {0表示不连通}
function search(city):integer;{求城市city到城市E的最短距离}
begin
if city=E then search←0;
else begin
min:=maxint;
for i取遍所有城市 do
if dist>0 and (i∈s)
then begin
s←s-;
j←dist+search(i);{递归调用搜索过程}
s←s+;
if j<min then min←j;
end;
search←min;
end;
begin
s←除E外所有城市；
dist←search(A);
end.
【效率评价】采用深度搜索的时间复杂度是W(n!)，效率很低。主要的原因就在于重复计算了很多路径值。如果把每次计算得到的最短距离保存下来就可以节省很多时间，于是产生了动态规划的思路。
【动态规划】从城市A出发，按照与城市A的路径长度划分阶段。
阶段0包含的出发城市有{A}
阶段1包含的城市有{B1，B2}
阶段2包含的城市有{C1，C2，C3，D，C4}
阶段3包含的城市有{D1，D2，D3}
阶段4包含的城市有{E}
这种划分的性质如下：
（1）阶段 i 的取值只与阶段 i+1 有关，阶段 i+1 的取值对阶段 i 的取值产生影响；
（2）每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。
从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市A，得到如下算法：
map←两个城市之间的距离数组
dist←0；
for k←3 downto 0 do
for x 取遍k阶段的所有城市 do
begin
dist←∞；
for y取遍k+1阶段的所有城市 do
if dist+map<dist
then dist←dist+map;
end;
输出dist;
[ 本帖最后由 kon3155 于 2009-2-25 12:56 编辑 ]
一、动态规划程序设计的基本概念
1、阶段k
将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每个阶段的解。设阶段变量为k。
2、状态Sk
各阶段开始的客观条件叫做状态，常用Sk表示各阶段的状态变量，Sk是k阶段的状态集合。
每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移。
将各阶段按照一定的次序排列好之后，对于阶段i的状态只能由阶段i+1的状态通过状态转移方程得来，与其他状态没有关系，尤其是未发生的状态没有关系。换句话说，每个状态都是“过去历史的一个完整总结”。就个特性称为“无后效性”。
3、决策
当各阶段的状态取定以后，就可以作出不同的决定，从而确定下一个阶段的状态，这种决定称为决策。表示决策的变量称为决策变量，常用Uk(Sk)表示第k阶段当状态为Sk时的决策变量，某个状态的决策可能有多个，以Dk(Sk)表示决策集合。
决策是问题解的属性。决策的目的就是“确定下一个阶段的状态”。
4、最优策略
在某一阶段的所有策略中，如有一个策略最优对于当前问题最优，则称最优策略。无论先前初始状态及初始策略如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。这就是最优化原理。
5、最优指标函数
用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为Fk(Sk)。最优指标函数其实就是我们真正关心的问题的解。
二、动态规划程序设计的一般步骤
1、确定问题的研究对象，即状态。对于一个动态规划程序设计来说，状态的设计与存储比阶段的划分更重要，因为阶段只是一些可以等同处理的状态的集合，状态的选定对整个问题的处理起了决定性的作用。选定状态必须满足如下两点：
① 状态必须完全描述出事物的性质，两个不同的事物的状态是不同的。
② 必须存在状态与状态之间的“转移方程”，以便可以由初始状态逐渐转化为目标状态。
2、划分阶段，确定阶段之间的状态转移方程。
3、考察此问题可否用动态规划程序设计方法解决，即问题是否具备最优子结构和无后效性的特征
4、如果发现问题目前不能用动态规划程序设计方法解决，则调整阶段的划分和状态的定义，使其具备最优子结构和无后效性的特征。
三、程序设计一般格式：
Fn(Sn)←某个初始值；
for k←n-1 downto 1 do
for S 取遍所有状态 do
for U 取遍所有决策 do
Fk(Sk)取最优决策 ；
【骑士游历问题】
设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。
输入：
m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标)
输出：
路径数目（若不存在，则输出0）
【分析】
本题可以使用深度搜索发求解，但是效率很低，当路径很多时，不可能在短时间内出解。可以采用动态规划的设计思想。
从（x1,y1）位置出发，按照由左到右的顺序定义阶段的方向。位于（x2,y2）的左方且可达（x2,y2）的跳马位置集合都是（x2,y2）的子问题，起点至（x2,y2）的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。
阶段i：中国象棋马当前的列位置（x1≤i≤x2）
状态j：中国象棋马在i列的行位置（1≤i≤m）
状态转移方程map：起点（x1,y1）至（i,j）的路径数目
具体算法如下：
fillchar(map,sizeof(map),0);
map←1；
for i←x1+1 to x2 do
for j←1 to m do
map←map+map+map+map;
writeln(map);
【参考程序】
【最长递增子序列】
给定数列A1,A2,...An，求最长递增子序列
输入：
第一行一个整数n，表示有n个数(n<=1000)
第二行n个整数，用空格隔开。
输出：
最长递增子序列长度。
【分析】
在求以Ai为末元素的最长递增子序列时，找到所有序号在Ai前面且小于Ai的元素Aj，即j<i且Aj<Ai。如果这样的元素存在，那么对所有Aj,都有一个以Aj为末元素的最长递增子序列的长度S(j)，把其中最大的S(j)选出来，那么S(i)就等于最大的S(j)加上1，即以Ai为末元素的最长递增子序列，等于以使S(j)最大的那个Aj为末元素的递增子序列最末再加上Ai；如果这样的元素不存在，那么Ai自身构成一个长度为1的以Ai为末元素的递增子序列。
阶段i:以第i个数为末元素
状态S(i):以第i个数为末元素的可能递增序列长度
转移方程：S(i+1)←max{S(i)}+1
【算法】
S:=1; {以第一个元素为末元素的递增序列长度肯定是1}
For i←2 to n do
For j←1 to i-1 do
Begin
搜索A前面比A小的数A，得到对应的S;
S←max{S}+1;
End;
Write(max{S});
【参考程序】
[ 本帖最后由 kon3155 于 2009-2-25 14:26 编辑 ]
【合唱队形】
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti，Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
【输入文件】
输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
【输出文件】
输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
【样例输入】
8
186 186 150 200 160 130 197 220
【样例输出】
4
【数据规模】
对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。
【分析】
假设第i位同学为最高个，则对其左边序列求最长递增序列长度，对其右边序列求最长递减序列长度，然后两者相加再减1（因为第i位同学被重复计算了一次）即可得到整个合唱队形的长度。可以利用两次动态规划求解，时间效率为O(N2)
依次枚举每一位同学为最高个，则N次之枚举后得到N个合唱队形长度，取其中最大值，然后(N-合唱队形最大值)即所求。 这样总的时间效率为O(N3)
【石子合并】
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
【输入文件】
包含两行，第1 行是正整数n（1<=n<=100），表示有n堆石子。
第2行有n个数，分别表示每堆石子的个数。
【输出文件】
输出两行。
第1 行中的数是最小得分；第2 行中的数是最大得分。
【输入样例】
4
4 4 5 9
【输出样例】
43
54
【分析】
本题初看以为可以使用贪心法解决问题，但是事实上因为有必须相邻两堆才能合并这个条件在，用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。例如下面这个例子：
6
3 4 6 5 4 2
如果使用贪心法求最小得分，应该是如下的合并步骤：
第一次合并 3 4 6 5 4 2 2,3合并得分是５
第二次合并 5 4 6 5 4 5,4合并得分是9
第三次合并 9 6 5 4 5,4合并得分是9
第四次合并 9 6 9 9,6合并得分是15
第五次合并 15 9 15,9合并得分是24
总得分＝5＋9＋9＋15＋24＝62
但是如果采用如下合并方法，却可以得到比上面得分更少的方法：
第一次合并 3 4 6 5 4 2 3,4合并得分是7
第二次合并 7 6 5 4 2 7,6合并得分是13
第三次合并 13 5 4 2 4,2合并得分是6
第四次合并 13 5 6 5,6合并得分是11
第五次合并 13 11 13,11合并得分是24
总得分＝7＋13＋6＋11＋24＝61
由此我们知道本题是不可以使用贪心法求解的，上例中第五次合并石子数分别为13和11的相邻两堆。 这两堆石头分别由最初 的第1，2，3堆（石头数分别为3，4，6）和第4，5，6堆（石头数分别为5，4，2）经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N－2次合并的得分总和最优。为了实现这一目标，我们将第１个序列又一分为二：第１、２堆构成子序列１，第３堆为子序列２。第一次合并子序列１中的两堆，得分７；第二次再将之与子序列２的一堆合并，得分13。显然对于第１个子序列来说，这样的合并方案是最优的。同样，我们将第２个子序列也一分为二；第４堆为子序列１，第５，６堆构成子序列２。第三次合 并子序列２中的２堆，得分６；第四次再将之与子序列１中的一堆合并，得分13。显然对于第二个子序列来说，这样的合并方案也是最优的。由此得出一个结论──６堆石子经过这样的５次合并后，得分的总和最小。
动态规划思路：
阶段i：石子的每一次合并过程，先两两合并，再三三合并，...最后N堆合并
状态s：每一阶段中各个不同合并方法的石子合并总得分。
决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案
具体来说我们应该定义一个数组s用来表示合并方法，i表示从编号为i的石头开始合并，j表示从i开始数j堆进行合并，s为合并的最优得分。
对于上面的例子来说，初始阶段就是s,s,s,s,s,s，因为一开始还没有合并，所以这些值应该全部为0。
第二阶段：两两合并过程如下，其中sum(i,j)表示从i开始数j个数的和
s=s+s+sum(1,2)
s=s+s+sum(2,2)
s=s+s+sum(3,2)
s=s+s+sum(4,2)
s=s+s+sum(5,2)
s=s+s+sum(6,2)
第三阶段：三三合并可以拆成两两合并，拆分方法有两种，前两个为一组或后两个为一组
s=s+s+sum(1,3)或s=s+s+sum(1,3)，取其最优
s=s+s+sum(2,3)或s=s+s+sum(2,3)，取其最优
.
.
.
第四阶段：四四合并的拆分方法用三种，同理求出三种分法的得分，取其最优即可。以后第五阶段、第六阶段依次类推，最后在第六阶段中找出最优答案即可。
由此得到算法框架如下：
For j←2 to n do {枚举阶段，从两两合并开始计算}
For i←1 to n do {计算当前阶段的n种不同状态的值}
For k←1 to j-1 do {枚举不同的分段方法}
begin
If i+k>n then t←(i+k) mod n else t←i+k {最后一个连第一个的情况处理}
s←最优{s+s+sum} {sum表示从i开始数j个数的和}
end;
【参考程序】