CF1175G Yet Another Partiton Problem

给定一个数组 $a_1, a_2, \dots, a_n$，你需要将其分成 $k$ 个子段（每个元素恰好属于一个子段）。 一个子段 $a_l, a_{l+1}, \dots, a_r$ 的权值定义为 $(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$。一个划分的权值是所有子段权值之和。 请你找到权值最小的划分方案。

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \times 10^4$，$1 \le k \le \min(100, n)$），分别表示数组 $a$ 的长度和划分的子段数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \times 10^4$），表示数组 $a$。

输出一个整数，表示所有可能划分中最小的权值。

第一个样例的最优划分为：$6$ $1$ $7$ $|$ $4$。 第二个样例的最优划分为：$6$ $|$ $1$ $|$ $7$ $4$。 第三个样例的一个最优划分为：$5$ $|$ $1$ $5$ $|$ $1$ $|$ $5$。 由 ChatGPT 4.1 翻译