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

!!!!!!!!这个解法好神仙!!!!!!!!

感谢机房大佬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