如何使用LIS解决10635 uva

如何从最长公共子序列减少到O（nlog n）问题的最长增加子序列10635 uva。我需要一些关于应用逻辑来解决问题的帮助。如何使用LIS解决10635 uva

2012-05-23 whitepearl

对于两个角色之一（假设公主）的路线的每一步，按照王子的顺序分配此步骤的编号。第一次观察 - 王子序列中没有出现的所有步骤立即被删除 - 它们不能成为常见动作序列的一部分。

现在我们有一系列数字代表王子移动顺序中的索引。我们应该选择一个递增的子序列（因为我们应该按照与王子相同的顺序访问单元格）增加该序列的最大长度。敲响任何钟声？

希望这会有所帮助。

2012-05-23 16:14:08

如果您在回复的第一行中给出了“在王子序列中分配此步骤的数量”的更精确和清晰的定义，将不胜感激。 – whitepearl

每个字符的路径是一个数组，您可以在给定步骤中访问单元格。所以你给这个王子保留了这个数组，并且你通过了公主的单元格，并且为王子阵列中的每个单元格指定了这个单元格在王子数组中的索引，从而指出了不存在的单元格王子的阵列。现在你需要对你得到的数字（即indecies）进行LIS。希望这更清楚。 –

如果对于公主阵列的每个元素，我们在王子阵列中找到对应的元素，这变成O（nm）算法。这破坏了为这个问题使用O（nlog n）LIS的目的。我理解你在帖子中提到的内容，甚至实现了同样的功能，并得到了TLE :(。如果我在任何地方出错或者有其他方法来解决问题，请纠正我。 – whitepearl

回答