《高中信息技术 全国青少年奥林匹克联赛教案 动态规划实例分析及程序实现》由会员分享，可在线阅读，更多相关《高中信息技术 全国青少年奥林匹克联赛教案 动态规划实例分析及程序实现（14页珍藏版）》请在金锄头文库上搜索。
1、全国青少年信息学奥林匹克联赛动态规划实例分析及程序实现一、数字三角形（图.）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1三角形行数100；三角形中的数字为整数0，1，99；输入数据：由INPUT.TXT文件中首先读到的是三角形的行数。在例子中INPUT.TXT表示如下：573 88 1 02 7 4 44 5 2 6 5输出数据：把最大总和（整数）写入OUTPUT.TXT文件。上例为：30（图.） 二、算法分析只要对该题稍加分析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路
2、径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。设：k（k）从第阶段中的点k至三角形顶点有一条最佳路径， 该路径所经过的数字的总和最大，k（k）表示为这个数字和；由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设k1阶段中某点k沿左斜线向下的点；k2阶段中某点k沿右斜线向下的点；k（k1）阶段中k1的
3、数字；k（k2）阶段中k2的数字；因而可写出顺推关系式k（k）k-1（k）k（k1），k-1（k）k（k2）0（0）；，经过一次顺推，便可分别求出由顶至底个数的条路径，在这条路径所经过的个数字和中，最大值即为正确答案。 三、程序分析根据上述顺推关系，我们编写程序如下：Program ID1P1;ConstMaxn = 100;TypeNode = RecordVal, Tot : Integer 当前格数字; 从1,1到当前格的路径所经过的数字和 End;VarList : Array 1.Maxn, 1.Maxn of Node; 计算表 N, Max, 行数, 最大总和 I, J : In
4、teger; 辅助变量 Fi : Text; 文件变量 Procedure Init;BeginAssign(Fi, INPUT.TXT); 文件名和文件变量连接 Reset(Fi); 文件读准备 Readln(Fi, N); 读三角形行数 For i := 1 to N Do 读入三角形各格的数字 For j := 1 to i Do Read(Fi, Listi, j.Val);Close(Fi)End;initProcedure Main;BeginList1, 1.Tot := List1, 1.Val; 从1,1位置开始往下顺推 For i := 2 to N DoFor j :=
5、1 to i Do BeginListi, j.Tot := -1; 从1,1至i,j的数字和初始化 If (j 1) And(Listi - 1, j - 1.Tot + Listi, j.Val Listi, j.Tot) ThenListi, j.Tot := Listi - 1, j - 1.Tot + Listi, j.Val; 若从i-1,j-1选择右斜线向下会使1,1至i,j的数字和最大,则决策该步 If (j i) And(Listi - 1, j.Tot + Listi, j.Val Listi, j.Tot) ThenListi, j.Tot := Listi - 1, j
6、.Tot + Listi, j.Val 若从i-1,j选择左斜线向下会使1,1至i,j的数字和最大,则决策该步 End; forMax := 1; 1,1至底行各点的N条路径所经过的数字和中,选择最大的一个输出 For i := 2 to N Do If ListN, i.Tot ListN, Max.Tot ThenMax := i;Writeln(ListN, Max.Tot) 输出最大总和 End; mainBeginInit; 读入数字三角形 Main 求最大总和 End.main 二、Problem : 打鼹鼠Contents: 有个n*n个格子，在m个时间点上的不定格子里有数量不等
7、的鼹鼠出现，机器人每次只能向前后左右移动一个格子，问最多机器人能打多少鼹鼠？ (n=1000, m=10000)Type: 动态规划 Difficulty: 2 Source: HNOI2004_day_*_*Solution : a) 记得学OI不到几个月，高一刚上来就做的这道题.着实郁闷了半天,有一个思路是开1000*1000 的数组乱搞忘了可以过几个来着.b) 又翻到这道题的时候是2月份了.发现 fi表示：如果机器人最后打死的老鼠是第i只，这种情况下机器人最多可以打死多少老鼠。就可以了,然后我赫然发现108 div 2次的若干基本操作是要TLE的c) 鉴于这道题郁闷的理论时间复杂度无法优
8、化，我请教了朱老师，原来动态规划枚举顺序也有其优化技巧，由于思路不是自己的，仅作简要介绍：a) (1).将更快、更容易“短路”的判断放在前面b) (2).将内部循环（j的循环）倒序，逼近最优解d) 我的计算机有点慢 总分 = 100.0第一题：mole 得分 = 100.0 用时 = 7.16smole-0(mole1.In) 结果 = 正确 得分 = 10.0 用时 = 0.01s 空间 = 0.71Mmole-1(mole2.In) 结果 = 正确 得分 = 10.0 用时 = 0.01s 空间 = 0.71Mmole-2(mole3.In) 结果 = 正确 得分 = 10.0 用时 =
9、0.02s 空间 = 0.71Mmole-3(mole4.In) 结果 = 正确 得分 = 10.0 用时 = 0.98s 空间 = 0.71Mmole-4(mole5.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71Mmole-5(mole6.In) 结果 = 正确 得分 = 10.0 用时 = 1.00s 空间 = 0.71Mmole-6(mole7.In) 结果 = 正确 得分 = 10.0 用时 = 1.05s 空间 = 0.71Mmole-7(mole8.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71Mmole
10、-8(mole9.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71Mmole-9(mole10.In) 结果 = 正确 得分 = 10.0 用时 = 1.02s 空间 = 0.71M分析设第i只老鼠在第Ti个时刻出现在(xi, yi)，T1=T2=T3=Tm。假设机器人打死了L只老鼠，不妨设这些老鼠的编号是a1, a2, , aL。显然对于任意的i(1=i=|xai+1-xai|+|yai+1-yai|。fi表示：如果机器人最后打死的老鼠是第i只，这种情况下机器人最多可以打死多少老鼠。可以列出方程：fi = maxfj+1, 11=j=|xi-xj|+|yi
11、-yj|最后求的答案就是maxfi(1=i=m) 此算法时间复杂度为O(m2)。考虑到m=10000，而时限只有1second，所以还必须进行一些代码优化。 因为ji，所以实际的循环次数只有m2/2次，也就是至多5000万左右。 我们看看下面的代码：for i := 1 to m do begin fi := 0; for j := 1 to i 1 do if (abs(xi-xj) + abs(yi-yj) fi) then fi := fj; fi:=fi+1;end; 它无疑是正确的。但是循环中的判断语句大有文章可做：上面的代码每次都铁定至少要执行3次减法、2次绝对值、1次比较运算。这
12、无疑是极度昂贵的操作代价。所以我们可以将(fjfi)这个比较“便宜”的判断条件提到前面，变成如下形式： if (fjfi) and (abs(xi-xj) + abs(yi-yj)=Ti-Tj) then这样做的好处是一旦fj=fi就可以执行“短路操作”（也就是说后面那一大截速度很慢的操作都可以避免。不过编译的时候一定要记得设成$B+） 实践证明速度是快了不少。可是对于1second的时限还是不能胜任。实战游戏经验告诉我们，机器人一般情况下不可能打完一只老鼠之后就跑到很远的地方去寻找新的猎物，肯定是一路上碰到一点老鼠就打一点。所以机器人相继打的两只老鼠的出现时间不可能相差太远。因此在方程fi = maxfj+1, 11=j=|xi-xj|+|yi-yj|之中，使得i达到最优的j肯定不会和i差得太远。同时在我们的判断语句中：if (fjfi) and (abs(xi-xj) + abs(yi-yj)fi) and (abs(xi-xj) + abs(yi-yj)=Ti-Tj) then fi := fj; fi:=fi+1;end
