题解

思路

将数组排序不改变所有下标子集的集合。对于非负整数随机变量，有“层蛋糕”恒等式：所有子序列美丽值之和等于，对每个 $d\ge1$，美丽值至少为 $d$ 的长度 $k$ 子序列数量之和。

固定 $d$。排序后选出的下标 $p_1<p_2<\cdots<p_k$ 合法，当且仅当每一对相邻选中值满足

令 $f[c][i]$ 为选择 $c$ 个数且最后一个数为 $a_i$ 的方案数。转移来源是所有满足 $a_j\le a_i-d$ 的 $j<i$，它们构成前缀。

做法

对每个 $d=1,2,\ldots,\lfloor(a_n-a_1)/(k-1)\rfloor$ 做一次动态规划。对上一层 DP 维护前缀和，并用单调指针找出每个 $i$ 可转移前缀的右端点，于是每层为 $O(n)$。

若 $d(k-1)>a_n-a_1$，不可能选出 $k$ 个两两相邻差至少为 $d$ 的值，因此无需继续枚举。

子任务 1 可直接枚举所有大小为 $k$ 的下标集合；子任务 2 可在固定 $d$ 时显式枚举最后两个下标做二次转移。

复杂度

设值域跨度为 $V=a_n-a_1$。时间复杂度为

空间复杂度为 $O(n)$。