1149.旅游预算

时限：1000ms 内存限制：10000K  总时限：3000ms

描述

一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则： 若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。

 

输入

第一行为起点到终点的距离（实数） 第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用（精确到分），第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。

 

输出

共两行，每行都有换行 第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，最后一个数据后也输出空格，此外没有多余的空格。

 

输入样例

516.3

15.7 22.1 20.87 3

125.4 1.259

297.9 1.129

345.2 0.999

 

输出样例

38.09 1

2

解析：额，我刚看到这道题，好像不是很会做，让我解析一下。每当走到一个站，检查一下油箱里的油，若超过一半且能坚持到下一站，按题意就坚决不能加油，若到不了则肯定要加油。若少于一半，且到不了下一站，肯定要加油，若少于一半但能到达下一站，就需要斟酌一下了，可以选择加满或者不加，加满是因为若这里的油价便宜就加满，不加满是因为这里的油价贵。

对于实现，dp函数里面传进去一个参数 i ，返回值应是 i 到终点站的最小花费（所以问题的答案就是dp(0)）。对于当前的 i ，此时需要检查它是否能到达下一站，注意此时必定是满油状态。那么遍历i 后边到终点站的每一个站，看能否到达其中的一些站。此时可能会发生的情况有如下几种：情况一直接能到达终点站，那么直接退出，返回0就可以；情况二看是否已经遍历过此站，如果有那么肯定已经记录了此站到终点站的最小花费（因为dp函数就是得到第 i 个站到终点站的最下花费，所以肯定会有备忘录来记录；情况三就需要进入for函数，遍历后边的每一个 j 站，若能到达j 站且油箱还剩一半的油，此时按规定不能加油，所以不加油直接跳到下一个站即j+1检查，若当前的j站就是终点站则不需要加油，花费记为0即可，若不是这两种，就要加油，然后把费用记录下来，即更新当前i到终点站的费用等与刚刚加油的费用（也就是i到j的费用）加上j到终点站的费用，同时记录下来加油的站点j。

此时有个问题可能大家会注意到，如果我当前油量不足一半但是我可以到达下一站，那么我可以选择加油或者不加油，然后比较这两者的代价谁更小才记录啊。这个是正确的，这个解法也恰恰就遵循了这个，因为在遍历i后边的每个站点j时，我都是在当前的j站点加了油，这就是第一种加油的情况，然后我把这种方法的代价给更新到备忘录里边了，但是此时还是在for循环里边，循环到下一个j时，此时我是在上一个站点不加油的方法，此时我又得出了新的不加油方法的代价，此时与备忘录进行代价小的比较，将代价小的写入。

此时的dp代码大概如下：