描述

給定一個序列，初始為空。現在我們將1到N的數字插入到序列中，每次將一個數字插入到一個特定的位置。每插入一個數字，我們都想知道此時最長上升子序列長度是多少？

---

分析

• 用 treap 就可以很方便地維護插入操作, 然后一遍 dfs 求出最后的序列
• 之后就是 lis 算法的拓展
  
  • lis 算法 nlogn 的解法 : (基于貪心和二分查找)
    用 lis[] 數組存一個上升的序列, 依次從序列中取出一個元素 x, 在lis中二分查找第一個大于它的元素(如果有)替換為 x, 如果 x 是最大的, 就插入到序列尾部.
    這樣做的正確性就在于用 x 替換掉比它大的元素, 結果一定不會變差.
  • 本題解法 :
    因為有個很特殊的性質——第一個插入的一定是1, 第二個一定是2…第n個是n
    回顧lis中的操作, 在序列中取出 x, 如果序列尾的元素小于x, 那么序列中所有元素都既小于x又先于 x 被插入, 所以可判斷在剛剛插入x時最長上升子序列長度就等于現在的序列的長度; 另一種情況, 如果序列尾元素大于x, 二分查找第一個大于x的元素, 用x替換它, 此時x之前的元素也滿足了既小于x又先于 x 被插入, 以x結尾的序列的最長上升子序列的長度就是x的下標了. 但是, 插入x后最長上升子序列不一定以x結尾, 也就是最長上升子序列長度一定不會隨插入元素增多而變短. 掃一遍結果維護一下就可以了.

---

代碼

https://code.csdn.net/snippets/609906

總結

以上是生活随笔為你收集整理的BZOJ-3173-最长上升子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。