algorithm - 使用 "The longest increasing subsequence algorithm (nlgn)"增加子序列的数量

Question

供引用:我正在解决嵌套娃娃问题:http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2353

我已经写了寻找最长递增子序列的部分(nlgn 版本)。例如，如果序列如下:1 2 3 1 2 1

1. 我找到最大的子序列:“1 2 3”并将其从原始序列。序列变为 1 2 1。

2. 我找到最大的子序列:“1 2”，然后再次将其删除。序列变为1。

3. 我找到最大的子序列:“1”并将其删除。序列变为空。

所以答案是3，总共3个递增子序列

我的问题是我遇到了 TLE(时间限制)，我需要一种更好的方法来计算子序列。有关于使用“Dilworth 定理”的提示，但我不确定如何应用它。

Answer 1

算法

如果我对这个问题的理解是正确的，那么你正在尝试找到可以打包每个玩偶的最小嵌套玩偶数量，你的算法是在每个阶段贪婪地制作最大的玩偶(最大的意思是它包含最多的玩偶)件)并重复，直到所有娃娃都被包装好。

换句话说，您是从偏序集构建链。

Dilworth's theorem说:

the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains

因此您可以通过计算单个反链中的元素来计算链的数量。

您可以采用与目前非常相似的方式构建反链，即按宽度降序排列玩偶，然后找到高度内最长的递增子序列。

请注意，使用这种方法，您可以通过测量反链的长度来获得答案，并且您只需要运行一次最长递增子序列算法，因此速度应该会快很多。

例子

在您的 (1, 1), (1, 1), (2, 2), (3, 3), (1, 1), (2, 2), (1, 1) 示例中，我们首先按宽度降序排列:

(3, 3), 
(2, 2), 
(2, 2), 
(1, 1), 
(1, 1), 
(1, 1), 
(1, 1)

然后提取高度:

3,2,2,1,1,1,1

然后找到最长的递增子序列(注意每个元素必须等于或高于前一个所以严格来说你找到最长的非递减子序列):

1,1,1,1

这是长度 4，所以答案是 4。