题解

思路

若把一个连续段全部变成该段最小值，长度为 $L$ 的段恰需 $L-1$ 次操作：从最小值位置逐步向两侧传播即可。任意操作结果也可按最终相同值的连续块划分，因此只需决定数组的分段方式。

做法

令 $dp[i][j]$ 表示处理前 $i$ 个元素、使用 $j$ 次操作的最小和。枚举最后一段长度 $L$，其中 $1\le L\le j+1$，维护这段的最小值 $m$，转移为

最终取 $dp[n][0\ldots k]$ 的最小值。

正确性证明

长度为 $L$ 的连续段可以从段内最小元素开始，以 $L-1$ 次相邻复制把整段变为最小值，且任何更小段和都不可能低于 $L$ 倍原段最小值。另一方面，任意操作序列中相同来源值传播到的位置形成连续块；每个长度为 $L$ 的块至少使用 $L-1$ 次复制。动态规划枚举最后一块的全部长度和操作数，故既能构造每个转移，也覆盖所有最优结果。取不超过 $k$ 次操作的最小值即为答案。

复杂度分析

时间复杂度 $O(nk^2)$，空间复杂度 $O(nk)$。