MX0802测 B

· · 个人记录

很难不设状态 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)

然后考虑优化。

很难发现