285水果店果篮最小成本问题

题解

问题概述

小 C 需要将 n 个编号为 1 到 n 的水果打包成若干个果篮。每个果篮最多可以容纳 m 个水果，且果篮中的水果编号必须连续。每个果篮的成本由以下公式决定：

[ \text{成本} = k \times \left\lfloor \frac{u + v}{2} \right\rfloor + s ]

其中：

• k 是果篮中水果的数量。
• u 是果篮中水果的最大体积。
• v 是果篮中水果的最小体积。
• s 是一个常数。
• (\left\lfloor x \right\rfloor) 表示对 x 进行下取整。

目标是找到一种打包方式，使得总成本最小。

解题思路

本题可以使用动态规划的方法来解决。设 f[i] 表示前 i 个水果的最小总成本。状态转移方程的核心思想是考虑最后一个果篮包含的水果数量，并选择使总成本最小的分割方式。

具体步骤

1. 初始化：

   • 定义一个数组 f，长度为 n + 1，初始化所有元素为正无穷大，表示初始状态下成本无限大。
   • 设置 f[0] = 0，表示不放入任何水果时的成本为 0。

2. 动态规划转移：

   • 遍历每一个水果位置 i（从 1 到 n），尝试将第 i 个水果作为当前果篮的结尾。
   • 对于每个位置 i，向前遍历最多 m 个水果（因为每个果篮最多容纳 m 个水果），计算当前果篮的成本，并更新 f[i]。
   • 在遍历过程中，维护当前果篮中水果的最小值 mi 和最大值 mx，以及当前果篮中水果的数量 cnt。
   • 计算当前果篮的成本，并与之前的最小成本进行比较，取较小值作为 f[i] 的值。
   • 如果当前果篮中的水果数量达到 m，则停止遍历，避免超过果篮的最大容量。

3. 结果输出：

   • 最终，f[n] 即为将所有 n 个水果打包的最小总成本。

代码解析

inf = float('inf')

def solution(n: int, m: int, s: int, a: list) -> int:
    # f[i] 表示放入i个水果的最小价值
    f = [inf] * (n + 1)
    f[0] = 0
    a = [0] + a  # 使水果编号从1开始

    for i in range(1, n + 1):
        cnt = 0
        mi = inf
        mx = -inf
        for j in range(i, 0, -1):
            mi = min(mi, a[j])
            mx = max(mx, a[j])
            cnt += 1
            # 计算当前分组的成本
            current_cost = f[j - 1] + s + ((mx + mi) // 2) * cnt
            # 更新f[i]为当前最小成本
            f[i] = min(f[i], current_cost)
            if cnt >= m:
                break  # 超过最大容量，停止遍历
    return f[n]

复杂度分析

• 时间复杂度： O(n * m)，其中 n 是水果的数量，m 是果篮的最大容量。对于每个水果位置，需要遍历最多 m 个位置。
• 空间复杂度： O(n)，用于存储动态规划数组 f。