供参考:我正在解决嵌套娃娃问题: uva.onlinejudge/index.php?option=onlinejudge&page=show_problem&problem=2353
我已经写了部分以找到最长的递增子序列(nlgn版本)。例如,如果序列如下:1 2 3 1 2 1
我发现最大的子序列: 1 2 3 ,然后从原始序列中将其删除。该序列变为1 2 1。
我找到最大的子序列: 1 2,然后再次将其删除。该序列变为1。
我找到最大的子序列: 1,然后将其删除。序列变为空。
所以答案是3,3个增加的子序列
我的问题是我获得了TLE(时间限制),我需要一种更好的计数子序列的方法。关于使用迪尔沃思定理的提示,但我不确定如何应用。
解决方案算法
如果我正确理解了这个问题,尝试找出可以装满每个娃娃的最小数量的嵌套娃娃,而您的算法是在每个阶段贪婪地制作最大的娃娃(从最大的意义上讲,它包含最多的碎片),然后重复进行直到所有的娃娃都装满为止。 p>
换句话说,您是从部分有序集合中构造链。
迪尔沃斯定理说:
the任何反链中元素的最大数量等于集合中任何划分为链的最小链的数量
您可以通过计算单个反链中的元素来计算链数。
您可以按照与当前操作类似的方式构造反链,方法是:订购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,1th是长度4,所以答案是4。
For reference: I'm solving the nested dolls problem: uva.onlinejudge/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
I find the largest subsequence: "1 2 3" and I remove it from the original sequence. The sequence becomes 1 2 1.
I find the largest subsequence: "1 2" and I remove it again. The sequence becomes 1.
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:
the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains
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.
ExampleIn 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,1then 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,1this is of length 4, so the answer is 4.
更多推荐
使用“最长的增加子序列算法(nlgn)”的增加的子序列的数量为0。
发布评论