长度为k的递增子序列数

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在尝试理解该算法，该算法使我在时间O（n k log（n））中增加了数组中长度K的子序列。我知道如何使用O（k * n ^

2）算法解决同样的问题。我查了一下，发现此解决方案使用了BIT（分域树）和DP。我也找到了一些代码，但我一直无法理解。

这是我访问过的一些有用的链接。

在这里，SO

Topcoder论坛

随机网页

如果有人可以帮助我理解该算法，我将不胜感激。

回答：

我从这里重现我的算法，其中解释了其逻辑：

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] *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 *2*       
      dp[i, p] += num[j]

您可以使用段树或二进制索引树进行优化*1*和*2*使用。这些将用于有效处理num阵列上的以下操作：

  • 鉴于(x, v)加v至num[x]（相关*1*）;

  • 给定x，求和num[1] + num[2] + ... + num[x]（与有关*2*）。

对于这两种数据结构来说，这都是微不足道的问题。

这将具有复杂性O(n*k*log S)，这S是数组中值的上限。这可能足够，也可能不够。为此O(n*k*log

n)，您需要在运行上述算法之前规范化数组的值。规范化意味着将所有数组值转换为小于或等于的值n。所以这：

5235 223 1000 40 40

成为：

4 2 3 1 1

这可以通过排序（保留原始索引）来完成。

以上是 长度为k的递增子序列数 的全部内容， 来源链接： utcz.com/qa/430611.html

回到顶部