626F

发现直接做非常困难，考虑将能力值排序后从小到大插入。 令 $f_{i,j,l}$ 表示前 $i$ 个人，有 $j$ 组需要继续加人，不和谐度之和**恰好**为 $l$ 的方案数。此时加入一个人对不和谐度之和产生的贡献为 $t=j\times(a_{i+1}-a_i)$。分三种情况转移： - 组数加一 ......

简要题意： 有$n$个学生，每个学生有一个能力值$a_i$。现在要把这些学生分成一些(任意数量的)组，每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过$k$的分组方案总数。 首先，无论我们怎么选，每个组的不和谐度只与他们组内的能力值最大者和能力值最小 ......

模拟赛垫底哥来补题了。 先排序，考虑到原来的弱智状态难以描述，我们可以这样写： $f_{i, j, k}$ 表示前 $i$ 个，$j$ 段未闭合，目前的不协调值为 $k$。 然后喜提 $n^2 \sum a_i$ 的时间复杂的。 然后就是经典 trick time，这个可以看作很多线段。然后 $a_ ......