P1594:护卫队题解

思路

一看这道题就知道是划分车辆的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;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注