如何将问题的最长公共(public)子序列还原为 O(nlog n) 最长递增子序列 10635 uva 。我需要一些有关解决问题的逻辑的帮助。
最佳答案
对于两个角色之一(假设是公主)路线的每一步,按照王子的顺序分配该步骤的编号。
第一个观察结果 - 王子序列中不存在的所有步骤都会立即删除 - 它们不能成为常见 Action 序列的一部分。
现在我们有一个数字序列,代表王子的移动序列中的索引。我们应该选择该序列的最大长度的递增子序列(递增是因为我们应该以与王子相同的顺序访问单元格)。敲响警钟吗?
希望这有帮助。
关于algorithm - 如何使用LIS解决10635 uva,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10723794/