本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-02 14:26:58

很难不设状态 $f(i, j)$ 表示前 $i$ 个数，已经选的和是 $j$ 的最少代价，那么很难不注意到显然的转移

$$f(i, j) = \min\limits_{k=0}^j f(i - 1, j - k) + w(k)$$

其中，$w(k)$ 是比 $k$ 大的数的数量。很难不做到 $O(nm^2)$

然后考虑优化。

很难发现