海外求购信息网_网站怎么做好_aso推广平台_开发app需要多少资金

前言：写这个题目的时候想了好久，但是只能想到一个复杂度为$n^3$的写法，最外层的循环枚举分割的次数（最多为1000），里层的循环分别枚举左边界和右边界，其实这么麻烦就是为了解决i*k的问题

正确的思路应该是转换成后缀来写

---

题目地址

class Solution:def minimumCost(self, nums: List[int], cost: List[int], k: int) -> int:n = len(nums)s = list(accumulate(cost, initial=0))  # cost 的前缀和f = [0] * (n + 1)for i, sum_num in enumerate(accumulate(nums), 1):  # 这里把 i 加一了，下面不用加一f[i] = min(f[j] + sum_num * (s[i] - s[j]) + k * (s[n] - s[j])for j in range(i))return f[n]

要注意下标问题