题目内容

硬件安全模块（HSM）要按编号顺序轮换 $n$ 把业务密钥。第 $i$ 把密钥的敏感度为 $\texttt{sens}[i]$（下标从 $0$ 开始）。

密钥必须按原顺序处理，但可以切成若干连续批次：一批对应一段 $[L,R]$（闭区间，下标），整批在同一次 HSM 会话里轮换。会话次数不能超过 maxBatches。

一批 $[L,R]$ 的费用为：

即：每次开会付固定的 baseCost，再按「批内敏感度之和 × 批长度」收取材料体积费。不同批次的费用相加。

请返回：在批次个数不超过 maxBatches 的前提下，轮换完全部密钥的最小总费用。输入保证 $1\le \textit{maxBatches}\le n$，因此至少存在「一把密钥一批」的合法方案。

请实现：

minRotateCost(sens: int[], baseCost: int, maxBatches: int) -> long

（费用可能超过 32 位有符号整数，请使用 64 位整数。）

输入描述

三行：

• 第一行：整数数组 sens
• 第二行：整数 baseCost
• 第三行：整数 maxBatches

约束：

• $1 \le n \le 200$，$n=\texttt{sens.length}$
• $1 \le \texttt{sens}[i] \le 10^4$
• $1 \le \textit{baseCost} \le 10^9$
• $1 \le \textit{maxBatches} \le n$

输出描述

一个整数：最小总费用。

样例1

输入：

[1, 3, 2]
5
3

输出：

20

说明：划分为 [1,3] / [2]。
第一批：$5+(1+3)\times 2=13$；第二批：$5+2\times 1=7$；合计 $20$。
三把各一批是 $21$，一整批是 $5+6\times 3=23$，都更大。

样例2

输入：

[2, 2]
10
1

输出：

18

说明：只能一批：$10+(2+2)\times 2=18$。

样例3

输入：

[1, 1, 1]
100
3

输出：

109

说明：baseCost 很大，应尽量合并。一整批 $100+3\times 3=109$，拆开只会更贵。