经典的动态规划入门练习题

4.旅游预算 一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则： 若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。 输入格式： 从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况： 第一行为起点到终点的距离（实数） 第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第