algorithm - 如何使用LIS解决10635 uva

Question

对于问题10635 uva，如何从最长公共子序列减少到 O(nlog n) 最长增加子序列。我需要一些有关解决问题的逻辑的帮助。

Answer 1

对于两个角色之一的路线的每一步（假设是公主），在王子的序列中分配这一步的编号。

首先观察 - 王子序列中不存在的所有步骤都会立即删除 - 它们不能成为常见动作序列的一部分。

现在我们有一个数字序列，代表王子移动序列中的索引。我们应该选择该序列的最大长度的增加子序列（增加，因为我们应该以与王子相同的顺序访问细胞）。敲响任何铃铛？

希望这可以帮助。