自动搬运

查看原文

来自洛谷，原作者为

	Richard_H 法 小 师

搬运于2025-08-24 21:53:44，当前版本为作者最后更新于2023-11-07 20:21:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

切了这个题，你也可以成为法拉利策略师

首先这个题的输入数据就比较多，好好整理一下再仔细思考这个题。

下面定义一下文中会出现的变量名的含义：

• 比赛的总圈数 int n

• 理论上，没有油的空车跑一圈所需的时间 double emtt

• 每增加 $1$ 公升汽油，赛车跑一圈所增加的时间 double inct

• 理论上，没有油的空车跑一圈所消耗的油量 double emtg

• 每增加 $1$ 公升汽油，赛车跑一圈所增加的油量损耗 double incg

• 每次进站所需花费的时间 double pitt

• 每次进站后，每加 $1$ 公升汽油，所需花费的时间 double pitg

（解释一下，其中的 $t$ 表示的是时间，$g$ 表示的是汽油，$emt$ 表示空车，$inc$ 表示增加，$pit$ 表示进站，方便记忆，免得搞混）

在搞懂了题目之后不难发现这玩意是动态规划，暂定 $f[i]$ 表示的是维斯塔潘舒马赫跑了 $i$ 圈后最短时间，利用贪心的思想，每次进站或者到达终点的时候肯定是把油箱跑得一滴油都不剩了，所以我们先得预处理出来恰好跑 $i$ 圈耗油是多少。

首先，如果只跑一圈，我们可以列出来这样一个关于耗油量 $gas$ 的方程：

$$\begin{aligned} gas - emtg - incg \times gas = 0 \end{aligned}$$

然后同理可得，对于跑 $i$ 圈的耗油量 $gas[i]$ 的方程：

$$\begin{aligned} (gas[i] - emtg - incg \times gas[i]) = gas[i - 1] \end{aligned}$$

由此得到递推式

$$gas[i] = \frac{gas[i - 1] + emtg}{1 - incg}$$

然后由于我们每次跑 $i$ 圈的时间与油量也有关，所以我们每次还需要预处理出来跑 $i$ 圈正好把油箱跑空的时间是多少。这个东西按照题目的要求计算即可。

接下来就是正经的 dp 部分，$f[i]$ 表示的就是跑了 $i$ 圈正好进站（或者到达终点）的最短时间，可以枚举上一次进站时间是第几圈，然后转移。在遍历的时候我们假装他是维修区发车，但是不计算进站和加油的时间。然后他又要输出方案，所以每次记录一下是从哪里转移过来的，最后用一下 stack 按顺序输出。

时间复杂度 $\Theta (n^2)$

---

贴代码！（目前 30ms，最快哦）

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
typedef long long lol;
typedef pair<int, int> pii;
typedef unsigned int uin;

const int N = 505;
int n;
double emtt, inct, emtg, incg, pitt, pitg;
double gas[N], lap[N], f[N];
int pre[N];

int main () {
    scanf ("%d%lf%lf%lf%lf%lf%lf", &n, &emtt, &inct, &emtg, &incg, &pitt, &pitg);

    for (int i(1); i <= n; ++ i ) 
        gas[i] = (gas[i - 1] + emtg) / (1 - incg), 
        lap[i] = lap[i - 1] + emtt + gas[i] * inct, 
        f[i] = 1e18;
    
    for (int i (1); i <= n; ++ i ) 
        for (int j (0); j < i; ++ j ) 
            if (j) 
            {
                double t = f[j] + pitt + gas[i - j] * pitg + lap[i - j];
                if (f[i] > t) 
                    f[i] = t, pre[i] = j;
            }
            else 
            {
                double t = f[j] + lap[i - j];
                if (f[i] > t) 
                    f[i] = t, pre[i] = j;
            }
    
    stack <pii> s;
    int u = n;
    while (pre[u]) 
        s.push(pii (pre[u], u - pre[u])), 
        u = pre[u];

    printf ("%.3lf %.3lf %d\n", f[n], gas[u], s.size());
    while (!s.empty()) 
        printf ("%d %.3lf\n", s.top().first, gas[s.top().second]), s.pop();
    
    return 0;
}