T565410 「2025 YAC Round 3」前往东之国的新年列车

「2025 YAC Round 3」E 题  图片来源：[pixiv_id=119317805](https://www.pixiv.net/artworks/119317805)

新年列车一共有 $m$ 排，每一排有许多个座位。现在有 $n$ 名乘客等待登上列车，他们排成一队，从左至右依次一个一个地上车。 如果第 $i$ 名乘客的座位位于第 $r_i$ 排，那么 TA 上车难度等于在其前面上车的且座位位于第 $1, 2, \ldots, r_i - 1$ 排的乘客人数之和。 全部乘客登上列车的总难度是所有乘客上车难度总和。 为了让乘客们更容易上车，需要将整个列车分为 $k$ 节车厢，每节车厢中的排数必须是连续的。 然后分成 $k$ 段执行上车流程，在每个阶段，选择一个车厢，座位在该车厢内的乘客按照他们在初始队列中的顺序上车。 请你找到列车划分为 $k$ 节车厢的最优方案，输出登上列车总难度的最小值。

第一行输入三个整数 $n, m, k$（$1\le n, m\le 1000$，$1 \le k \le \min(m, 50)$），分别表示乘客数量、座位总排数 和 划分车厢个数。 第二行输入 $n$ 个整数 $r_1, r_2, \ldots, r_n$（$1 \le r_i \le m$），表示每个乘客的座位排数。

输出一个整数表示答案。

#### 样例解释 在划分车厢之前，每个乘客的上车难度依次为：$0,1,2,1,3,5,3,0$ 划分 $2$ 节车厢的最优方案如下： 将 $1 \sim 3$ 排划分到一个车厢，这节车厢的乘客上车队列为 $1,3,2,1$，每个乘客的上车难度依次为 $0,1,1,0$。故这节车厢的乘客上车总难度为 $2$； 将 $4 \sim 6$ 排划分到一个车厢，这节车厢的乘客上车队列为 $5,4,6,4$，每个乘客的上车难度依次为 $0,0,2,0$。故这节车厢的乘客上车总难度也为 $2$。 最终所有乘客上车总难度为 $4$。