↓Skip to main content
  1. Posts/

LeetCode-2735 收集巧克力

·1 min·
Table of Contents

LeetCode-2735 收集巧克力 #

Solution 1 #

对于某个类型 $i$, 在第 $j$ 次操作后可以使用 $nums[i + j]$ 来获取. 从类型考虑不好计算操作的代价, 因此不妨直接枚举操作的次数. 假设进行了 $t$ 次操作, 对于类型 $i$ 来说, 它可以在第 $j$ 次 ($0\leq j\leq t$)操作后以 $nums[i + j]$ 的代价取到. 因此最小代价为 $$ \min_{t}(tx+\sum_{i}(\min_{0\leq j\leq t}nums[i+j])) $$ 在枚举次数 $t$ 时, 取第 $i$ 类的代价可以不断维护.

代码如下:

class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        ans = 1e20
        cost = [[0 for _ in range(n + 1)] for _ in range(n)]
        for t in range(n + 1):
            res = x * t
            for i in range(n):
                cost[i][t] = nums[i] if t == 0 else min(cost[i][t - 1], nums[(i + t) % n])
                res += cost[i][t]
            ans = min(ans, res)
        return ans