加载中…2014NOIP普及组初赛 二、问题求解2.如图所示，图中每条边上的数字表示该边的长度，则……
(2015-10-28 10:31:49)
标签：
2014noip初赛动态规划 |
分类： noip |
2014NOIP普及组初赛
二、问题求解
http://s12/bmiddle/001zBkZkgy6WygMz8tZcb&690二、问题求解2.如图所示，图中每条边上的数字表示该边的长度，则……" TITLE="2014NOIP普及组初赛 二、问题求解2.如图所示，图中每条边上的数字表示该边的长度，则……" />
这个题目是动态规划的一个变型题目，从A到E划分为四个阶段，每个阶段都要决策，前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策，产生后一阶段的状态。
=min{2+6,4}=4
2.如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是（
）。
这个题目是动态规划的一个变型题目，从A到E划分为四个阶段，每个阶段都要决策，前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策，产生后一阶段的状态。
http://s1/mw690/001zBkZkgy6WyiHEOHK10&690二、问题求解2.如图所示，图中每条边上的数字表示该边的长度，则……" TITLE="2014NOIP普及组初赛 二、问题求解2.如图所示，图中每条边上的数字表示该边的长度，则……" />
我们可以用倒推的方法，求A到E的最短距离。用k来表示阶段。
我们可以用倒推的方法，求A到E的最短距离。用k来表示阶段。
第一步：k=4 有 d4（F，E）来表示F到E的距离，4表示第四阶段。
f4(F)=6
第二步：k=3
有四条路到F，用d3（C，E）、d3（C，F）、d3（D，F）、d3（D，E）来表示这四条路，3表示第三阶段。
f3(C)=min{d3（C，E）、d3（C，F）}
=min{8，1+6}=7
f3(D)=min{d3（D，F）、d3（D，E）}
第三步：k=2 有
f2(B)=min{d2(B,C),d2(B,D)}
=min{1+7,7+4}=8
f2(G)=min{d2(G,C),d2(G,D)}
=min{2+7,4+4}=8
第四步：k=1有
f1(A)=min{d1(A,B),d1(A,G),d1(A,F)}
=min{3+8,4+8,6+6}=11
答案：11 。
喜欢
0
赠金笔