解题思路

• 问题可抽象为：将按顺序的包裹序列划分为若干个连续分段，每个分段选择一辆货车（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)
  • 因为向后累加 sum 单调增，一旦 sum > 50 即可提前停止当前 i 的向前枚举。

• 异常处理：若存在单个包裹重量 > 50 吨，则无解，直接输出 -1。

复杂度分析

• 外层遍历 i=1..N，内层对每个 i 最多向前扩展至 sum>50 即止，最坏为 O(N^2)；N≤1024 完全可行。
• 时间复杂度：O(N^2)
• 空间复杂度：O(N)（仅需一维 DP 数组）

代码实现

Python

# -*- coding: utf-8 -*-
import sys

INF = 10**18

def min_cost(weights):
    # 若存在单个包裹超过50吨，无法运输
    if any(w > 50 for w in weights):
        return -1
    n = len(weights)
    dp = [INF] * (n + 1)
    dp[0] = 0
    # 枚举前i个包裹的最优解
    for i in range(1, n + 1):
        s = 0  # 区间和 sum(j..i)
        # 向前扩展起点 j
        for j in range(i, 0, -1):
            s += weights[j - 1]
            if s > 50:  # 超过所有车型容量，提前停止
                break
            # 使用A车
            if s <= 30:
                dp[i] = min(dp[i], dp[j - 1] + 400)
            # 使用B车
            if s <= 50:
                dp[i] = min(dp[i], dp[j - 1] + 600)
    return dp[n] if dp[n] < INF else -1

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        print(-1)
        return
    n = int(data[0])
    weights = list(map(int, data[1:1 + n]))
    ans = min_cost(weights)
    print(ans)

if __name__ == "__main__":
    main()

Java

// -*- coding: utf-8 -*-
import java.util.*;

/**
 * ACM 风格主类 Main
 */
public class Main {

    // 计算最小运输成本的函数（在主函数外部）
    public static int minCost(int[] w) {
        // 若存在单个包裹超过50吨，无法运输
        for (int x : w) {
            if (x > 50) return -1;
        }
        int n = w.length;
        final int INF = 1_000_000_000;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        // 枚举前 i 个包裹
        for (int i = 1; i <= n; i++) {
            int s = 0; // 区间和 sum(j..i)
            // 向前扩展起点 j
            for (int j = i; j >= 1; j--) {
                s += w[j - 1];
                if (s > 50) break; // 超过所有车型容量，提前停止
                if (s <= 30) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 400); // A车
                }
                if (s <= 50) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 600); // B车
                }
            }
        }
        return dp[n] >= INF ? -1 : dp[n];
    }

    // 主函数：读入与输出
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) {
            System.out.println(-1);
            return;
        }
        int n = sc.nextInt();
        int[] w = new int[n];
        for (int i = 0; i < n; i++) w[i] = sc.nextInt();
        int ans = minCost(w);
        System.out.println(ans);
    }
}

C++

// -*- coding: utf-8 -*-
#include <bits/stdc++.h>
using namespace std;

// 在主函数外部实现功能：计算最小运输成本
long long min_cost(const vector<int>& w) {
    // 若存在单个包裹超过50吨，无法运输
    for (int x : w) if (x > 50) return -1;
    int n = (int)w.size();
    const long long INF = (long long)4e18;
    vector<long long> dp(n + 1, INF);
    dp[0] = 0;

    // 枚举前 i 个包裹
    for (int i = 1; i <= n; ++i) {
        int s = 0; // 区间和 sum(j..i)
        // 向前扩展起点 j
        for (int j = i; j >= 1; --j) {
            s += w[j - 1];
            if (s > 50) break; // 超过所有车型容量，提前停止
            if (s <= 30) dp[i] = min(dp[i], dp[j - 1] + 400); // A车
            if (s <= 50) dp[i] = min(dp[i], dp[j - 1] + 600); // B车
        }
    }
    return dp[n] >= INF ? -1 : dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) {
        cout << -1 << "\n";
        return 0;
    }
    vector<int> w(n);
    for (int i = 0; i < n; ++i) cin >> w[i];
    long long ans = min_cost(w);
    cout << ans << "\n";
    return 0;
}

题目内容

电商大促结束后, 多多需要将 $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$