比赛链接

Solved by qxforever.

给 $n$ 个数，分为三组，使三组和的 max-min 最小。$n\le 400$ ，$a_i \le 30$

考虑 dp，设 $f_{i,j,k}$ 表示前 $i$ 个数，第二组减第一组为 $j$ ，第三组减第一组为 $k$ 是否可行。设两组差的范围为 $m$ ，那么时间和空间复杂度均为 $O(n\times m^2)$ 。猜想在 random_shuffle 下，$m$ 的范围不必很大也能找到最优解。

在实现中，考虑空间限制，取 $m=750$ ，单次计算耗时 ~ 300ms 。考虑时间限制，随机 $8$ 次取最优解通过了本题。