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)\)。

发表评论

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