全国青少年信息学奥林匹克联赛动态规划实例分析及程序实现一、数字三角形（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。●每一步可沿左斜线向下或右斜线向下走；●1＜三角形行数≤100；●三角形中的数字为整数0，1，…99；输入数据：由INPUT.TXT文件中首先读到的是三角形的行数。在例子中INPUT.TXT表示如下：5738810274445265输出数据：把最大总和（整数）写入OUTPUT.TXT文件。上例为：30７３８８１０２７４４４５２６５（图３.１－１）二、算法分析只要对该题稍加分析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n,则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，……，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。设：ｆk（Ｕk）━━从第ｋ阶段中的点Ｕk至三角形顶点有一条最佳路径，该路径所经过的数字的总和最大，ｆk（Ｕk）表示为这个数字和；由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设Ｕk1━━ｋ－１阶段中某点Ｕk沿左斜线向下的点；Ｕk2━━ｋ－１阶段中某点Ｕk沿右斜线向下的点；ｄk（Ｕk1）━━ｋ阶段中Ｕk1的数字；ｄk（Ｕk2）━━ｋ阶段中Ｕk2的数字；因而可写出顺推关系式ｆk（Ｕk）＝ｍａｘ｛ｆk-1（Ｕk）＋ｄk（Ｕk1），ｆk-1（Ｕk）＋ｄk（Ｕk2）｝ｆ0（Ｕ0）＝０；Ｋ＝１，２，３，４，……ｎ经过一次顺推，便可分别求出由顶至底Ｎ个数的Ｎ条路径，在这Ｎ条路径所经过的Ｎ个数字和中，最大值即为正确答案。三、程序分析根据上述顺推关系，我们编写程序如下：ProgramID1P1;ConstMaxn=100;TypeNode=RecordVal,Tot:Integer{当前格数字;从[1,1]到当前格的路径所经过的数字和}End;VarList:Array[1..Maxn,1..Maxn]ofNode;{计算表}N,Max,{行数,最大总和}I,J:Integer;{辅助变量}Fi:Text;{文件变量}ProcedureInit;BeginAssign(Fi,'INPUT.TXT');{文件名和文件变量连接}Reset(Fi);{文件读准备}Readln(Fi,N);{读三角形行数}Fori:=1toNDo{读入三角形各格的数字}Forj:=1toiDoRead(Fi,List[i,j].Val);Close(Fi)End;{init}ProcedureMain;BeginList[1,1].Tot:=List[1,1].Val;{从[1,1]位置开始往下顺推}Fori:=2toNDoForj:=1toiDoBeginList[i,j].Tot:=-1;{从[1,1]至[i,j]的数字和初始化}If(j<>1)And(List[i-1,j-1].Tot+List[i,j].Val>List[i,j].Tot)ThenList[i,j].Tot:=List[i-1,j-1].Tot+List[i,j].Val;{若从[i-1,j-1]选择右斜线向下会使[1,1]至[i,j]的数字和最大,则决策该步}If(j<>i)And(List[i-1,j].Tot+List[i,j].Val>List[i,j].Tot)ThenList[i,j].Tot:=List[i-1,j].Tot+List[i,j].Val{若从[i-1,j]选择左斜线向下会使[1,1]至[i,j]的数字和最大,则决策该步}End;{for}Max:=1;{[1,1]至底行各点的N条路径所经过的数字和中,选择最大的一个输出}Fori:=2toNDoIfList[N,i].Tot>List[N,Max].TotThenMax:=i;Writeln(List[N,Max].Tot){输出最大总和}End;{main}BeginInit;{读入数字三角形}Main{求最大总和}End.{main}二、Problem:打鼹鼠Contents:有个n*n个格子，在m个时间点上的不定格子里有数量不等的鼹鼠出现，机器人每次只能向前后左右移动一个格子，问最多机器人能打多少鼹鼠？(n<=1000,m<=10000)Type:动态规划Difficulty:2Source:HNOI2004_day_*_*Solution:a)记得学OI不到几个月，高一刚上来就做的这道题..着实郁闷了半天,有一个思路是开1000*1000的数组乱搞…忘了可以过几个来着..b)又翻到这道题的时候是2月份了..发现f[i]表示：如果机器人最后打死的老鼠是第i只，这种情况下机器人最多可以打死多少老鼠。就可以了,然后我赫然发现10^8div2次的若干基本操作是要TLE的c)鉴于这道题郁闷的理论时间复杂度无法优化，我请教了朱老师，原来动态规划枚举顺序也有其优化技巧，由于思路不是自己的，仅作简要介绍...
