使用“最长的增加子序列算法（nlgn）”的增加的子序列的数量为0。

问题描述

供参考：我正在解决嵌套娃娃问题：

我已经写了部分以找到最长的递增子序列（nlgn版本）。例如，如果序列如下：1 2 3 1 2 1

1. 我发现最大的子序列： 1 2 3 ，然后从
   原始序列中将其删除。该序列变为1 2 1。




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




3. 我找到最大的子序列： 1，然后将其删除。序列变为空。

所以答案是3，3个增加的子序列

我的问题是我获得了TLE（时间限制），我需要一种更好的计数子序列的方法。关于使用迪尔沃思定理的提示，但我不确定如何应用。

解决方案

算法

如果我正确理解了这个问题，尝试找出可以装满每个娃娃的最小数量的嵌套娃娃，而您的算法是在每个阶段贪婪地制作最大的娃娃（从最大的意义上讲，它包含最多的碎片），然后重复进行直到所有的娃娃都装满为止。 p>

换句话说，您是从部分有序集合中构造链。

说：

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

您可以按照与当前操作类似的方式构造反链，方法是：订购t

请注意，通过这种方法，您可以通过测量反角的长度来获得答案-chain，您只需运行一次最长的递增子序列算法，因此它应该快得多。

示例

在（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 
  

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

For reference: I'm solving the nested dolls problem: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2353

I have written the portion to find the longest increasing subsequence (the nlgn version). For example if the sequence is the following: 1 2 3 1 2 1

1. I find the largest subsequence: "1 2 3" and I remove it from theoriginal sequence. The sequence becomes 1 2 1.

2. I find the largest subsequence: "1 2" and I remove it again. The sequence becomes 1.

3. I find the largest subsequence: "1" and I remove it. The sequence becomes empty.

So the answer is 3, 3 total increasing subsequences

My problem is that I'm getting TLE (time limit) and I need a better way of counting the subsequences. There is a hint about using "Dilworth's theorem" but I'm not sure how to apply it.

解决方案

Algorithm

If I understand the question correctly, you are trying to find the minimum number of nested dolls that can pack every doll, and your algorithm is to greedily make the biggest doll at each stage (biggest in the sense that it contains the most pieces) and repeat until all dolls are packed.

In other words, you are constructing chains from your partially ordered set.

Dilworth's theorem says:

and so you can compute the number of chains by counting the elements inside a single antichain.

You can construct the antichain in a very similar way to you are doing at the moment, by ordering the dolls by width in decreasing order and then finding the longest increasing subsequence within the heights.

Note, that with this method you get the answer by measuring the length of the anti-chain and you only need to run the longest increasing subsequence algorithm once so it should be a lot faster.

Example

In your example of (1, 1), (1, 1), (2, 2), (3, 3), (1, 1), (2, 2), (1, 1) we first sort by width in decreasing order:

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

and then extract the heights:

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

then find the longest increasing subsequence (note that each element must be the same or higher than the previous so strictly speaking you find the longest non-decreasing subsequence):

1,1,1,1

this is of length 4, so the answer is 4.

这篇关于使用“最长的增加子序列算法（nlgn）”的增加的子序列的数量为0。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！