P11114 [ROI 2024 Day 1] 小推车 题解

· · 题解

-1.前言

这道题开始真没思路，看了前一篇题解，茅塞顿开，也是给前一篇题解补充一点东西，再加上一点自己的东西。

前一篇题解把自己当成小推车，但是我就是小推车（Little_Cart）啊所以就来写一下

0.题意注意点

不可以卸下还装有饮料的瓶子，是指还装有饮料的瓶子剩余容量不会补充至 p。

同时，题意保证 k \leq m，这个其实挺重要的。

小推车开始是可以有饮料的，但是在题目中没有提到。

1.做法

上篇题解说到

题目中每个瓶子容积是一样的， 并且未空的瓶子不能重装饮料，这意味着可以预处理出来 w[i] 代表到 i 最少需要多少个空瓶子，p[i] 表示到 i 时去过去储藏室最多能装多少个空瓶子 ，v[i] 表示 i 到最近的储藏室并回到下一个服务位置的最小距离，f[i] 表示服务 1 到 i 最少走的步数。

可以预处理原因很简单，首先是小推车他必须按照从 1 到 n 的顺序走，还有一个最主要的原因，就是只要这个瓶子放了这种饮料，那么直到他没有变空之前，这个瓶子只能一直是这个饮料。这个事情是不会根据选取的 l 到 r 的区间去改变的。

此时 k \leq m 重要的原因也就明朗了，如果 k>m 就有可能出现乘客要第 m+1 种饮料，但是瓶子内部只有 1 到 m 的饮料，而且非空，这下子就上不去下不来卡在这里了。

预处理的方法也很简单，忽略加饮料需要去服务位置然后进行模拟即可。

- $f_i=\min(f_j+v_j+i-j-1)

关于可以使用单调队列维护 dp 的原因我认为是因为原式可以转化成如下形式：

所以单调队列维护的就是这个 val_j。

由于这道题 n 的最大值只有 10^6，所以可以直接使用优先队列维护，虽然多一个 \log 的复杂度。