洛谷1594 护卫队

算法竞赛 动态规划
编辑文章

显然用dp,用 $f[i]$ 表示前 $i$ 辆车过桥的最短时间,枚举上一个分组的最后一辆车 $j$ 进行转移,方程式为:

$$f[i]=min \begin{cases} f[i] \\ f[j-1]+len\div s[i] \times 60 & j<=i, \sum ^{i}_{k=j}w[k]<=wmax \end{cases}$$

其中 $tmax$ 是这一组中最长的过桥时间, $wmax$ 是桥的最大限重,$len$ 是桥的长度。

不过这题有坑,必须开long long,而且dp数组初始化需要 $1e15$ 才能过。

ll n,m,s[1005],w[1005],w_max,len;
double f[1005];

int main()
{
    w_max=read(); len=read(); n=read();
    for (int i=1;i<=n;i++) w[i]=read(),s[i]=read();
    for (int i=1;i<=n;i++) f[i]=1e15;
    for (int i=1;i<=n;i++)
    {
        ll w_now=0;
        double t_now=0;
        for (int j=i;j;j--)
        {
            w_now+=w[j];
            if (w_now>w_max) break;
            t_now=max(t_now,60.0*len/s[j]);
            f[i]=min(f[i],f[j-1]+t_now);
        }
    }
    printf("%.1f",f[n]);
    system("pause");
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空