DP-子序列问题(待完善

上升子序列

• 定义：在一个序列 \(a\) 中满足 $a_j < a_i $ 且 \(j<i\) 的子序列。

• \(e.g.\) 在序列 { \(0\) \(3\) \(2\) \(5\) \(1\) \(4\) } 中 { \(0\) \(1\) \(4\) } 与 { \(3\) \(5\) } 便是其中两个上升子序列。

最长上升子序列

• 定义：在满足上升子序列的同时，长度最长的子序列。

• \(e.g.\) 在序列 { \(0\) \(3\) \(2\) \(5\) \(1\) \(4\) } 中 { \(0\) \(1\) \(4\) } 与 { \(0\) \(2\) \(5\) } 是其中两个上最长升子序列，长度都为 \(3\) 。

• 求解：

  • \(O(n^2)\) 的 \(DP\) 设计状态为前 \(i\) 位最长子序列的长度为 \(j\) ，逐步转移即可。

  • \(O(n \log n)\) 树状数组加贪心解法：

    • 最长上升子序列本质为同时满足值单调递增与下标单调递增的最长子序列。

    • 由此，记录每个值的下标 \(a[i].id\) ，然后将数组按值排序，使序列满足值单调递增的条件。顺序遍历数组。更新时 \(i\) 时从第一个原下标和值都比自己小的地方转移即可。

      树状数组能够维护原序列中最长子序列的长度，并且因为数组有序，更新 \(i\) 时树状数组中已更新的值必然都小于等于 \(a[i].x\) ，所以直接从树状数组中第一处原序号在 \(i\) 之前的地方转移即可。

    • 核心代码：

      add(a[i].id,ask(a[i].id-1)/*查询原序列中满足j<a[i].id的最长子序列*/+1);