舒马赫的策略师

· · 题解

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

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

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

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

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

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

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

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

(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;
}