题目分析本题是一个汽车旅行预算问题。旅行者从起点出发驾驶汽车前往目的地沿途有若干加油站。旅行者需要支付汽油费用每加仑价格在各加油站不同以及每次停靠加油站时购买零食的2.002.002.00美元。需要计算从起点到目的地所需的最小总费用包括出发前在起点加满油箱的费用。驾驶规则如下出发时油箱是满的。司机只在必要时停靠加油站即当油箱内汽油超过半箱时除非无法到达下一个加油站或目的地否则不会停靠。每次停靠都会将油箱加满并支付2.002.002.00美元的零食费用。每笔费用四舍五入到最近的美分即小数点后两位。只需使用足够到达下一个加油站或目的地的汽油不需要安全余量。解题思路本题采用DFS\texttt{DFS}DFS深度优先搜索进行求解。数据处理为了方便处理将起点视为第000个站点距离为000价格为起点的油价将目的地视为最后一个站点距离为目的地距离价格为000。沿途的加油站按距离从小到大排列直接存入数组中。状态表示使用结构体driver\texttt{driver}driver表示当前状态包含当前所在加油站索引、已行驶距离和当前总花费单位为美分避免浮点精度问题。搜索策略从当前站点出发计算在满油状态下能够到达的最远距离endendend。如果endendend能够直接到达目的地则更新最小花费。否则遍历当前站点之后的所有可到达的加油站计算到达该加油站消耗的汽油量和加油后的剩余行驶里程。根据规则判断是否必须停靠如果剩余行驶里程能够到达下一个加油站且当前油箱油量超过半箱则可以选择不停靠使用continue\texttt{continue}continue跳过。如果需要停靠则计算本次花费汽油费用×\times×油价四舍五入取整加上200200200美分的零食费用。使用记忆化剪枝如果曾经以更小花费到达过该站点则跳过。更新状态并递归搜索。费用处理所有费用以美分为单位存储输出时转换为美元并正确格式化小数点后两位。代码实现// Budget Travel// UVa ID: 222// Verdict: Accepted// Submission Date: 2016-05-14// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 加油站结构体structstation{intindex;// 站点索引doublemilesFromOrigin;// 距离起点的距离英里doublepricePerGallon;// 每加仑价格美分intminimumCost;// 到达该站点时的最小花费美分};// 司机状态结构体structdriver{intindex;// 当前所在站点索引doublemilesTravel;// 已行驶距离英里inttotalCost;// 当前总花费美分};doubletotalDistance,capacityOfTank,costAtStart;// 总距离、油箱容量、起点加油费用doublemilesPerGallon,milesFromOrigin,pricePerGallon;// 每加仑英里数、临时变量intcounter,minimumCost;// 加油站数量、全局最小花费vectorstationstations;// 所有站点包含起点和终点// 深度优先搜索voiddfs(driver aDriver){// 当前满油状态下能到达的最远距离doubleendaDriver.milesTravelcapacityOfTank*milesPerGallon;// 如果能直接到达目的地if(endtotalDistance){// 更新最小花费if(minimumCost0||aDriver.totalCostminimumCost)minimumCostaDriver.totalCost;return;}// 遍历当前站点之后的可到达站点最后一个站点是目的地不在此遍历for(intiaDriver.index1;istations.size()-1;i){// 如果该站点在可到达范围内if(endstations[i].milesFromOrigin){// 计算到达该站点消耗的汽油量加仑doublegasolineUsed(stations[i].milesFromOrigin-aDriver.milesTravel)/milesPerGallon;// 加满后能额外行驶的里程英里doubletravel(capacityOfTank-gasolineUsed)*milesPerGallon;// 根据规则判断是否必须停靠// 如果加满后能到达下一个加油站且当前油量超过半箱则可以选择不停靠if(travel(stations[i1].milesFromOrigin-stations[i].milesFromOrigin)2*gasolineUsedcapacityOfTank)continue;// 创建新状态driver newDriveraDriver;// 添加本次加油费用四舍五入到美分newDriver.totalCostround(gasolineUsed*stations[i].pricePerGallon);// 添加零食费用2美元 200美分newDriver.totalCost200;// 记忆化剪枝如果曾经以更小花费到达过该站点则跳过if(stations[i].minimumCost0stations[i].minimumCostnewDriver.totalCost)continue;// 记录到达该站点时的最小花费stations[i].minimumCostnewDriver.totalCost;// 更新状态newDriver.milesTravelstations[i].milesFromOrigin;newDriver.indexi;// 继续递归搜索dfs(newDriver);}elsebreak;// 由于站点按距离排序后面的站点距离更远直接退出}}intmain(){intcases0;while(cintotalDistance){if(totalDistance0.0)break;stations.clear();// 读入油箱容量、每加仑英里数、起点加油费用、加油站数量cincapacityOfTankmilesPerGalloncostAtStartcounter;// 添加起点作为第0个站点费用为0暂不记录后续单独处理stations.push_back((station){0,milesFromOrigin,pricePerGallon,0});// 读入沿途加油站信息for(inti1;icounter;i){cinmilesFromOriginpricePerGallon;stations.push_back((station){i,milesFromOrigin,pricePerGallon,-1});}// 添加目的地作为最后一个站点油价为0stations.push_back((station){counter1,totalDistance,0.0,-1});// 输出数据集编号coutData Set #casesendl;// 初始化最小花费为 -1表示未找到minimumCost-1;// 初始化司机状态driver aDriver;aDriver.index0;// 从起点出发aDriver.totalCost(int)(costAtStart*100.0);// 起点加油费用转换为美分aDriver.milesTravel0.0;// 已行驶距离为0// 开始深度优先搜索dfs(aDriver);// 输出结果格式化为美元两位小数coutminimum cost $;cout(minimumCost/100);cout.;if(minimumCost%10010)cout0;cout(minimumCost%100);coutendl;}return0;}