问题描述
其实这是一个 SPOJ 的问题。
假设我有一个数组 1,2,2,10
。
日益子序列长度为3的是 1,2,4
和 1,3,4
(基础)的索引。
The increasing sub-sequences of length 3 are 1,2,4
and 1,3,4
(index based).
那么,答案是 2
。
推荐答案
让:
dp[i, j] = number of increasing subsequences of length j that end at i
这是简单的解决方案是在为O(n ^ 2 * K)
:
An easy solution is in O(n^2 * k)
:
for i = 1 to n do
dp[i, 1] = 1
for i = 1 to n do
for j = 1 to i - 1 do
if array[i] > array[j]
for p = 2 to k do
dp[i, p] += dp[j, p - 1]
答案是: DP [1,K] + DP [2,K] + ... + DP [N,K]
。
现在,这工作,但它是低效率的你给定约束,因为 N
可高达 10000
。 K
足够小,所以我们应该尽量找到一种方法来摆脱一个 N
。
Now, this works, but it is inefficient for your given constraints, since n
can go up to 10000
. k
is small enough, so we should try to find a way to get rid of an n
.
让我们尝试另一种方法。我们也有取值
- 上限的价值观在我们的数组。让我们试着找到与此相关的算法。
Let's try another approach. We also have S
- the upper bound on the values in our array. Let's try to find an algorithm in relation to this.
dp[i, j] = same as before
num[i] = how many subsequences that end with i (element, not index this time)
have a certain length
for i = 1 to n do
dp[i, 1] = 1
for p = 2 to k do // for each length this time
num = {0}
for i = 2 to n do
// note: dp[1, p > 1] = 0
// how many that end with the previous element
// have length p - 1
num[ array[i - 1] ] += dp[i - 1, p - 1]
// append the current element to all those smaller than it
// that end an increasing subsequence of length p - 1,
// creating an increasing subsequence of length p
for j = 1 to array[i] - 1 do
dp[i, p] += num[j]
这有复杂 O(N * K * S)
,但我们可以把它降低到 O(N * K *登录S)
很容易。我们所需要的是一种数据结构,可以让我们更有效地在一个范围内总结和更新的元素:段树,<一个href="http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees">binary索引树等。
This has complexity O(n * k * S)
, but we can reduce it to O(n * k * log S)
quite easily. All we need is a data structure that lets us efficiently sum and update elements in a range: segment trees, binary indexed trees etc.
这篇关于如何找到增加一定长度的子序列与二进制树索引的总数(BIT)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!