自动搬运

查看原文

来自洛谷，原作者为

	OIer_ACMer El pueblo unido jamás será vencido!

搬运于2025-08-24 21:42:07，当前版本为作者最后更新于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;
}