P1180 驾车旅游【洛谷算法习题】
P1180 驾车旅游
网页链接
P1180 驾车旅游
题目描述
如今许多普通百姓家有了私家车，一些人喜爱自己驾车从一个城市到另一个城市旅游。自己驾车旅游时总会碰到加油和吃饭的问题，在出发之前，驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表，列表中包括了所有加油站的位置及其每升的油价（如3.25 3.253.25元/L）。驾车者一般都有以下的习惯：
- 除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来；
- 在第一个停下的加油站总是将油箱加满；
- 在加油站加油的同时，买快餐等吃的东西花去20 2020元。
- 从起始城市出发时油箱总是满的。
- 加油站付钱总是精确到0.1 0.10.1元（四舍五入）。
- 驾车者都知道自己的汽车每升汽油能够行驶的里程数。
现在要你帮忙做的就是编写一个程序，计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用。
输入格式
第一行是一个实数，是从出发地到目的地的距离（单位：km）。
第二行是三个实数和一个整数，其中第一个实数是汽车油箱的最大容量（单位：L)；第二个实数是汽车每升油能行驶的公里数；第三个实数是汽车在出发地加满油箱时的费用（单位：元）；一个整数是1 11到50 5050间的数，表示从出发地到目的地线路上加油站的数目。
接下来n nn行都是两个实数，第一个数表示从出发地到某一个加油站的距离（单位：km）；第二个实数表示该加油站汽油的价格(单位：元)。
数据项中的每个数据都是正确的，不需判错。一条线路上的加油站根据其到出发地的距离递增排列并且都不会大于从出发地到目的地的距离。
输出格式
输出一个实数，即精确到0.1 0.10.1元的最小的加油和吃饭费用。
输入输出样例 #1
输入 #1
600 40 8.5 128 3 200 3.52 350 3.45 500 365输出 #1
13133.2解题思路
本题核心是深度优先搜索（DFS）+剪枝优化，严格模拟驾驶员的加油规则求解最小费用。首先解析总距离、油箱容量、车辆续航、初始油费和加油站信息，初始化费用上限。按照题目规则判断加油逻辑：油箱油量不足以抵达下一站则必须加满（支付油费+20元餐费）；剩余油量≥油箱一半则不加油；介于两者之间可自由选择加油或不加油。通过DFS递归遍历所有加油站，枚举合法选择，当当前费用超过最优解时直接剪枝，最终得到最小总费用，按要求精确到0.1元输出。算法适配n≤50的小规模数据，精准匹配所有规则。
总结
核心逻辑：严格遵循驾驶员的加油习惯，用DFS枚举所有合法方案，剪枝优化找到最小费用。
关键操作：递归判断加油条件，计算油费与餐费，通过剪枝减少无效递归分支。
效率保障：针对加油站数量≤50的小数据，DFS+剪枝高效求解，无冗余计算。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;doubleS,C,E,I,ans;intn;doubleK[55],P[55];voiddfs(inti,doublem,doublel){if(i>n){if(m<ans)ans=m;return;}if(m>ans)return;l-=(K[i]-K[i-1])/E;if(l*E<K[i+1]-K[i]){dfs(i+1,m+20+P[i]*(C-l),C);}elseif(l*2<C){dfs(i+1,m+20+P[i]*(C-l),C);dfs(i+1,m,l);}else{dfs(i+1,m,l);}}intmain(){cin>>S>>C>>E>>I>>n;ans=I;K[n+1]=S;for(inti=1;i<=n;i++){cin>>K[i]>>P[i];ans+=P[i]*C+20;}dfs(1,I,C);printf("%.1lf",ans);return0;}