题解

思路

把 $a$ 从小到大排序。考虑从左到右加入学生。一个尚未确定最大值的小组称为“未闭合小组”。若当前有 $j$ 个未闭合小组，而相邻两个值的差为 $d$，那么跨过这段距离会使总不平衡度增加 $jd$。

做法

令 $f[j][s]$ 表示已经处理完前缀、当前有 $j$ 个未闭合小组且已经产生的不平衡度为 $s$ 的方案数。加入当前学生时有四类操作：

1. 让他单独组成已经闭合的小组；
2. 放入某个未闭合小组并保持该组未闭合；
3. 用他开始一个新的未闭合小组；
4. 放入某个未闭合小组并将该组闭合。

前两类合计有 $j+1$ 种选择，第三类有 $1$ 种，第四类有 $j$ 种。因此在先加上 $j(a_i-a_{i-1})$ 后，分别转移到 $j,j+1,j-1$。只保留代价不超过 $k$ 的状态。最终将 $f[0][0\ldots k]$ 求和。

正确性来自如下不变式：每个已闭合小组的最小值和最大值都已经出现；每个未闭合小组只确定了最小值。跨过一段数轴距离时，恰好每个未闭合小组的不平衡度增加该距离。四类转移对当前学生在最终分组中的角色分类，互斥且完备，因此每个集合划分被恰好计数一次。

复杂度

时间复杂度为 $O(n^2k)$，空间复杂度为 $O(nk)$。

子任务 1 可以直接枚举限制增长序列表示的所有集合划分；子任务 2 可以枚举包含最小未选元素的子集作为下一组，做子集动态规划。