思路

一看这道题就知道是划分车辆的DP。一开始想的是F[前i辆车][划分次数j]=前i辆车划分j次的时间，然后发现这种写法很慢，而且在本题中没有说明划分的次数，我们只需要求前n辆车的解即可。

转移方程：F[i] = F[j-1] + L / (lowest_spd in [1,j])，转移条件是不超载的情况下。

这题比较毒瘤，int会被卡，double的无穷大必须要真·无穷大。

代码

// P1594.cpp
#include <iostream>
#include <iomanip>

using namespace std;

#define ll long long
const double INF = 9223372036854775807ll;
const ll maxn = 1100;
struct car
{
    double v, w;
} cars[maxn];
double W, L, N;
double F[maxn];

void DP()
{
    F[0] = 0;
    for (ll i = 1; i <= N; i++)
    {
        F[i] = (double)INF;
        double load = 0;
        double lspd = INF;
        for (ll j = i; j > 0; j--)
        {
            load += cars[j].w;
            if (load > W)
                break;
            lspd = min(lspd, cars[j].v);
            F[i] = min(F[i], F[j - 1] + L / lspd);
        }
    }
}

int main()
{
    cin >> W >> L >> N;
    for (ll i = 1; i <= N; i++)
        cin >> cars[i].w >> cars[i].v;
    DP();
    cout << fixed << setprecision(1) << F[(ll)N] * 60;
    return 0;
}