题解：P2836 加油问题

OIer_ACMer · 2024-08-05 23:24:25 · 题解

第一次十二分钟切一道蓝题。

题目解析：

本题由于 n \le 51，我们就直接从搜索思考，（毕竟这么小的数据不练习搜索真是浪费了）。

我们可以借用一点闫氏动态规划分析法的思想，找出最后一个不同点：是否在一个站加油。我们在深度优先搜索中设三个参数：wz 表示在那个油站，mon 表示此时花掉的钱，至于 oil，则表示此时邮箱的剩余油量，如果加油，那么我们要考虑是否满足在油箱里还有不少于最大容量一半的汽油，因为，这是题目条件，后续操作就是用当地油价乘以差值加上两块钱餐费。不加油的话，只用让 wz 加 1 就行了，就是直接去下一个站。

什么，你问我为什么在不加油时不用对 oil 操作，我要告诉你，我们在函数的一开始就要将 oil 减去从当前站到前一个站的耗油量，如果在最后更新 wz 算的话，额，也行。

最后，注意两个点，一个是要判断当前的点是否到达 n + 1 的位置，因为，我们在主函数中设 n + 1 为终点，并且将一开始输入的两点之间的总距离存入 n +1 的距离数组中，方便计算耗油量，到了终点不下车就不对了。

第二个，如果我们判断此时的 oil 已经小于目前站点到原来站点的耗油量，直接退出，不然的话将负数带进去算会出锅，懂得都懂。

代码如下：

#include <bits/stdc++.h>
using namespace std;
double dis, rl, w, mon;
int n;
struct node
{
    double jl, jg;
} zhan[1000009];
double ans = INT_MAX;
void dfs(int wz, double mon, double oil)
{
    if (oil < (zhan[wz].jl - zhan[wz - 1].jl) / w)
    {
        return;
    }
    else if (wz == n + 1)
    {
        ans = min(ans, mon);
        return;
    }
    oil -= (zhan[wz].jl - zhan[wz - 1].jl) / w;
    if (oil <= rl / 2)
    {
        dfs(wz + 1, mon + 2.00 + (1.0 * (zhan[wz].jg * (rl - oil)) / 100.0), rl); // 加油
    }
    dfs(wz + 1, mon, oil); // 不加油
}
int main()
{
    cin >> dis >> rl >> w >> mon;
    cin >> n;
    zhan[n + 1].jl = dis;
    zhan[0].jg = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> zhan[i].jl >> zhan[i].jg;
    }
    dfs(1, mon, rl);
    cout << fixed << setprecision(2) << ans;
    return 0;
}