题目内容

云平台要规划未来 $n$ 天每天开启多少算力实例。

第 $i$ 天（从 $0$ 开始）的最低需求是 $\texttt{load}[i]$，当天实际开启的实例数记为 $x_i$，必须满足：

约定：第 $0$ 天之前实例数为 $x_{-1}=0$（尚未开启任何实例）。

每天的费用

第 $i$ 天费用由两部分相加：

1. 运行费：$x_i \times \textit{runCost}$（按当天实例数计）
2. 伸缩费：$|x_i - x_{i-1}| \times \textit{changeCost}$（相对前一天增减多少实例，就按幅度收费）

总费用为这 $n$ 天费用之和。

变更次数限制

「变更」按天计数，与伸缩幅度无关：

• 若 $x_i \neq x_{i-1}$，记 1 次变更
• 若 $x_i = x_{i-1}$，不计变更

整个规划中变更总次数不得超过 maxChanges。因此第 $0$ 天若 $x_0\neq 0$，也会占用 1 次变更额度。

任务

在「每天满足最低需求」且「变更次数 $\le \textit{maxChanges}$」的前提下，求总费用的最小值。输入保证至少有一种合法方案。

请实现：

minComputeCost(load: int[], runCost: int, changeCost: int, maxChanges: int) -> int

输入描述

四行：

• 第一行：整型数组 load
• 第二行：整数 runCost
• 第三行：整数 changeCost
• 第四行：整数 maxChanges

约束：

• $1 \le n \le 80$（$n=\texttt{load.length}$）
• $0 \le \texttt{load}[i] \le 40$
• $1 \le \textit{runCost},\textit{changeCost} \le 1000$
• $1 \le \textit{maxChanges} \le n$（保证有解）

输出描述

一个整数：最小总费用。

样例1

输入：

[1, 3, 2]
5
2
3

输出：

38

说明：取 $x=(1,3,2)$，变更 $3$ 次。

总费用 $7+19+12=38$。

样例2

输入：

[1, 3, 2]
5
2
1

输出：

51

说明：maxChanges=1，不能天天改。最优是第 $0$ 天一次拉到 $3$，之后保持 $3,3,3$（仅变更 $1$ 次）：

总费用 $21+15+15=51$。

样例3

输入：

[2, 2, 2]
3
1
1

输出：

20

说明：取 $x=(2,2,2)$。仅第 $0$ 天 $0\to 2$ 计 1 次变更；运行费 $2\times 3\times 3=18$，伸缩费 $2$，合计 $20$。