［例４］最佳浏览路线问题

　　试题描述　某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。

　　阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从-１００到１００的整数，所有林荫道不打分。所有分值不可能全是负值。

　　例如下图是被打过分的某旅游区的街道图：

　　　　　　　　　
　　
　　阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。

　　试题背景　　这道题同样出自ＮＯＩ９７，＇９７国际大学生程序设计竞赛的第二题（吉尔的又一个骑车问题）与本题是属于本质相同的题目。

　　试题分析 由于林荫道不打分，也就是说，无论游客在林荫道中怎么走，都不会影响得分。因题可知，若游客需经过某一列的旅游街，则他一定要经过这一列的Ｍ条旅游街中分值最大的一条，才会使他所经路线的总分值最大。这是一种贪心策略。贪心策略的目的是降维，使题目所给出的一个矩阵便为一个数列。下一步便是如何对这个数列进行处理。在这一步，很多人用动态规划法求解，这种算法的时间复杂度为Ｏ（ｎ²），当林荫道较多时，效率明显下降。其实在这一步我们同样可以采用贪心法求解。这时的时间复杂度为Ｏ（ｎ）。

　　§6.1.2 贪心策略在求P类较优解问题中的应用

　　正如其他学科奥林匹克竞赛一样，国际信息学奥赛的发展同样经历了一个逐步成熟的发展过程。回顾十余年赛事的发展，我们不妨将国际信息学奥赛的发展分为两个阶段：第一阶段是1989-1996年，这一时期奥赛题目的特点是：试题全部为P类问题，且只允许求最优解，题目的设计强调对选手基本算法的掌握。第二阶段为1997年至今。在南非举行的IOI97中，命题方向一举突破传统模式，NPC类问题在竞赛中大量出现，每道题目到具有一定的实际背景，引进了崭新的程序评测机制。在求解P类问题时允许得出较优解并得到相应的分数。这些变化无疑更好地考察了选手的综合素质。在对P类较优解问题的求解过程中，贪心策略无疑扮演着重要角色。IOI97中的障碍物探测器问题便是运用贪心策略来求得较优解的P类问题。

　　[例5] 障碍物探测器问题

　　试题描述 有一个登陆舱（POD），里面装有许多障碍物探测车（MEV），将在火星表面着陆，着陆后，探测车离开登陆舱向相距不远的先期到达的传送器（Transmitter）移动。MEV一边移动，采集岩石（ROCK）标本，岩石由第一个访问到它的MEV所采集，每块岩石只能被采集一次，但是这以后，其他MEV可以从该处通过。探测车MEV不能通过有障碍的地面。

　　本题限定探测车MEV只能沿着格子向南或向东从登陆处向传送器transmitter移动，允许多个探测车MEV在同一时间占据同一位置。

　　警告：如果某个探测车MEV在到达传送器以前不能在继续合法前进时，则车中的石块必定不可挽回地全部丢失。

　　任务：计算机探测车的每一步移动，使其送到传送器的岩石标本的数量尽可能多。这两项都做到会使你的得分最高。

　　输入：火星表面上登陆舱POD和传送器之间的位置用网格P和Q表示，登陆舱POD的位置总是在（1，1）点，传送器的位置总是在（P，Q）点。

　　火星上的不同表面用三中不同的数字符号来表示：

　　● 0代表平坦无障碍
　　● 1代表障碍
　　● 2代表石块

　　输入文件的第一行为探测车的个数，第二行为P的值，第三行为Q的值。接下来的Q行为一个Q×P的矩阵。

　　输出：表示MEV移向transmitter的行动序列。每行包含探测车号和一个数，0或1，这里0表示向南移动，1表示向东移动。

　　得分：分数的计算将根据收集的岩石样本（取到传送器上）的数目，MEV到达传送器和不到达传送器的数目有关

　　● 非法移动将导致求解无效，并记作零分，当MEV的障碍物上移动或移出网格，即视为非法。
　　● 得分=（收集的样品并取到传送器上的数目+MEV到达传送器上的数目-MEV没有到达传送器上的数目）与应得的最大的数目之比（%）
　　● 最高分为100%，最低分为0%

　　试题背景 IOI'97中的第一试第一题。国际信息学奥赛中出现的第一道NPC类问题。1997年美国的探测器再次到达火星。火星及太空搜索引起了人们的广泛关注，此题便是以此为素材而创作的。

　　试题分析 关于迷宫问题相信每一个参加信息学奥赛的选手都不会陌生。对于不同的迷宫，我们可用搜索策略或动态规划进行求解。在本题中，无论运用哪种解题策略均不能得到问题的最优解，我们的任务是合理选择一种解题策略，使我们运用该策略得到的较优解尽可能地接近最优解。我们先来看一个例子（如图7所示）。对于一个探测车而言，我们运用动态规划的方法使探测车经过岩石最多的一条路线便可得到问题的最优解（如图8所示），这时共可收集到岩石10个。　

　　　　　　　　
　　　　　　　　　　　　　　　
　　当有2个探测车时，我们让第2辆探测车在图8的基础上从地图的起点S行进至终点f（如图9所示），这时我们共收集到岩石15个。而实际上两辆探测车可收集到地图中的全部岩石（共16个），

　　当探测车数量为3时，我们可以收集到全部的16个岩石。

　　我们可让从起点出发的每一辆探测车都收集到尽可能多的岩石，这实际上是一种贪心策略。对于本题而言，贪心策略并不能保证所得结果全部为最优解，但由于每一辆探测车都收集尽可能多的岩石，而对于由计算机随机产生的测试数据而言，岩石是比较均匀地分布在地图中的，于是我们认为：

　　探测车收集岩石数≈探测车所游历的地图空间

　　让每一辆探测车收集尽可能多的岩石，也就是让探测车经过尽可能大的地图空间。所以在探测车数量逐渐增多时，所有探测车所经过的地图空间越多，收集到的岩石也就越多，此时也就越接近最优解。
此题是否存在最优解呢？其实，我们可以用网络流的算法来解决此题。但实践证明，用网络流算法去求解本题所占空间较大，编程复杂度较高且程序调试起来较为困难，因此在实际比赛中，在限定的时间内用贪心策略完成对题目的求借不失为上策。