Codeforces Round #572 (Div. 1) C. Array Beauty

题意

我们称一个序列$\{b_i\}_{i=1}^k$的beauty值为$\min_{i \neq j} |b_i – b_j|$。 给定序列$\{a_i\}_{i=1}^n$,问所有长度为k的子序列的beauty值之和。

数据范围:$2 \leq k \leq n \leq 1000, 0 \leq a_i \leq 10^5$

题解

我们可以使用一个常见的技巧:令$P(t)$为所有beauty值大于等于t的长度为k的子序列个数,那么答案就是$ \sum_{t=1}^{\infty} P(t) $。

这样问题就变成了计数题。首先将输入序列排序,令$ p_t(i) = \max\{j : a_j – a_i \geq t\} $,那么转移就可以写成:$ f_t(i, j) = f_t(i, j-1) + f_t(i-1, p_t(j)) $,且$P(t)= f_t(k, n)$。可以在均摊$O(n^2)$时间内求出所有 $p_t(i)$的值,另外计算一个P(t)的值需要$O(nk)$时间。注意到P(t)是单调递减的,因此当出现P(t)=0时就不必继续计算了。这样的t不会超过$\frac{\max a}{k-1}$,因此总的复杂度为$O(n \max a)$。

发表评论

电子邮件地址不会被公开。 必填项已用*标注