!!!!!!!! 这个解法好神仙!!!!!!!!
感谢机房大佬 ZYM!!! 大佬太强了!!!!!!!
感觉很多算法只懂如何实现还是不行啊, 得了解他的具体思路和实现过程
比如我刚学 OI 几个月就学了最长不下降子序列, 让我写这道题, 就算是现在的我也写不好
就像之前写的题 -- 灾后重建, 几乎就是考对 FLOYD 的了解 (即使它很短, 不懂还是会想不到)
思路来源他的讲解, 这篇仅做记录
题面
思路分析
(一篇讲解最长不下降子序列的很棒的博客) https://www.cnblogs.com/milky-w/p/8431333.html
关于最长不下降子序列, 要求为 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
好的就是这些
ありがとうございます
来源: http://www.bubuko.com/infodetail-3264155.html