题意描述

　　本题由普通的旅行家预算问题发展而来，它与普通的旅行家问题有如下区别：
　　　1．只要能到达下一站，若油箱内的油不少于一半，则不得加油；
　　　2．必须加满油，且每次加油需要一点额外费用；
　　　3．加油时的费用是四舍五入的。

　　算法分析

　　由于本题有一些特殊的条件限制，不能像通常的旅行家问题那样用贪心算法来解决，因此我们考虑采用动态规划方法解题。
　　首先，我们先对所有加油站按照与起点的距离大小从小到大排序，这是解决本题的第一个步骤。
　　我们用full[i]表示从起点到达i站并停下来加满油所花费的最小总费用，cost[i]表示到达第j站的最小费用，则：
　　所有从i点加满油后可以到达的站j的cost值为cost[j]=min{cost[j],full[i]}；
　　同时，如从i出发到达j耗费了一半以上的油，则full[j]=min{full[i]＋在j站把油加满的费用}
　　最后的结果保存在cost[n+1]中（假设中点为第n＋1个加油站）。

　　参考程序