对于第 i 个任务,设目标储存罐编号为 j(即 Qi),目标是将第 j 个储存罐装满,那么选择从第 k(k≤j) 个储存罐开始注入液体,那么 [k,j] 这些储存罐被装满的液体均来自从第 k 个储存罐溢出后流下的液体。
选择从第 k(k≤j) 个储存罐开始注入液体,则需要使得[k+1,j] 这些储存罐都注满,成本为 Pk×i=k∑j(Ci−Vi)。答案即
t=1minj(Pk×i=k∑j(Ci−Vi))此外,代码中使用了一个 trick,就是对于每个任务,从 j 到 1 来枚举从每个储存罐开始注入液体(而不是从1到j),这样我们就可以维护这其中需要补充的液体量。因为如果是从 1 到 j 来枚举,则对于每次的需液量都需要 O(n) 去查询,导致总复杂度是O(n3) , 当然也可以直接使用前缀和来维护。
在一座自动化工厂中,有 n 个依次串联的液体储存罐,编号为 1 到 n。第 i 个储存罐的容量为 Ci,初始已存有 Vi 单位液体。当向某个储存罐 j 注入液体时,如果注满后仍有液体进入,多余的部分会沿管道自动流入下一个储存罐 j+1,并继续向后传递(若从最后一个储存罐溢出则排入废液池)。向储存罐 j 注入单位液体需要花费 Pj 的成本。
调度员收到了 m 个任务,每个任务要求将某个指定的储存罐恰好填满。每次任务开始前,所有储存罐的液量都会恢复为初始状态,任务之间互不影响。若任务的目标储存罐在初始状态下已经满了,则不需要任何操作,成本为 0。
现在需要计算出每个任务所需的最小总成本。
约束条件:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册