【球的序列】——最长上升子序列

！！！！！！！！这个解法好神仙！！！！！！！！

感谢机房大佬ZYM！！！大佬太强了！！！！！！！

感觉很多算法只懂如何实现还是不行啊，得了解他的具体思路和实现过程

比如我刚学OI几个月就学了最长不下降子序列，让我写这道题，就算是现在的我也写不好

就像之前写的题——灾后重建，几乎就是考对FLOYD的了解（即使它很短，不懂还是会想不到）

思路来源他的讲解，这篇仅做记录

 题面

 思路分析

（一篇讲解最长不下降子序列的很棒的博客）

 关于最长不下降子序列，要求为 i < j , a [ i ] < a [ j ] ;

我们再看这道题，取出 lj , lk ，满足j,k(j<k)， lj 在 A 中位置比 lk 在 A 中位置靠前，且 lj 在 B 中位置比 lk 在 B 中位置靠前

 那么我们可以把 a[ j ] 当做 i ， a [ j ] 当做 j

那么另开一个数组H，H [ a [ i ] ] = b [ i ] 

那么直接用求最长不下降子序列的求法即可（O ( N log N)）

然后没了

超神仙！！！！！！！

代码直接看大佬的，改天我自己A一遍后再填充把

OVER

好的就是这些

ありがとうございます

【球的序列】——最长上升子序列

原文：https://www.cnblogs.com/Phantomhive/p/11761603.html