解题思路

• 问题可抽象为：将按顺序的包裹序列划分为若干个连续分段，每个分段选择一辆货车（A：容量30吨、成本400；B：容量50吨、成本600），并使总成本最小。

• 核心算法：动态规划（DP） 设 dp[i] 表示运走前 i 个包裹的最小成本（dp[0]=0）。 对于每个终点 i，向前枚举起点 j（j<=i），计算区间和 sum(j..i)：

  • 若 sum(j..i) ≤ 30，可用 A 车：转移 dp[i] = min(dp[i], dp[j-1] + 400)
  • 若 sum(j..i) ≤ 50，可用 B 车：转移 dp[i] = min(dp[i], dp[j-1] + 600)

题目内容

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

• $A$ 型货车: 最大承重 $30$ 吨, 单次装载成本 $400$ 元
• $B$ 型货车: 最大承重 $50$ 吨, 单次装载成本 $600$ 元

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

输入描述

共两行:

1. 第一行包含 $1$ 个整数 $N (0<N<=1024)$ 表示总共的包裹数
2. 第二行包含 $N$ 个正整数, 表示每个包裹的重量 (单位: 吨)

输出描述

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

样例1

输入

5
15 16 14 10 20

输出

1000

说明

装车方案:

• 货车 $1$ ($A$车型): $10$ (吨) + $20$ (吨) = $30$ (吨) 成本 $400$ 元

• 货车 $2$ ($B$ 车型): $15$ (吨) +$16$ (吨) + $14$ (吨) = $45$ (吨) 成本 $600$ 元

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

样例2

输入

4
12 18 70 10

输出

-1

说明

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