P4460.第3题-多多要省钱

1000ms

Difficulty: 5

所属公司 : 拼多多

算法与标签>动态规划

题目内容

电商大促结束后, 多多需要将 $N$ 个包裹通过货车从仓库转运到快递中心, 包裹不可拆分 (需完整运输) 且包裹需要按输入顺序进行装车运输。现在多多手上只有两种规格的货车 (假定两种规格货车数量无上限) :

为降低运输成本, 多多需要制定最优装车方案, 在满足载重限制的前提下, 尽量省钱的完成所有包裹转运的最少运输成本。

共两行:

共一行, 一个整数, 表示最少需要的运输成本 (单位: 元), 若出现任何异常导致无法计算最小运输成本, 输出 $-1$

输入

5
15 16 14 10 20

输出

说明

装车方案:

货车 $1$ ( $A$ 车型): $10$ (吨) + $20$ (吨) = $30$ (吨) 成本 $400$ 元
货车 $2$ ( $B$ 车型): $15$ (吨) + $16$ (吨) + $14$ (吨) = $45$ (吨) 成本 $600$ 元

总计 $2$ 辆, 总成本 $1000$ 元, 无更优方案。

输入

4
12 18 70 10

输出

-1

说明

存在包裹 $70$ (吨), $A$ 车型和 $B$ 车型均无法运输, 因此当异常处理输出 $-1$

输入

预期输出（选填）