关于最长下降子序列的O(nlogn)解法

回复帖子

@dnbd 2020-09-17 00:04 回复

最长上升子序列(lis)的O(nlogn)解法已经是常识了,但是有没有大佬能提供一下最长下降子序列的O(nlogn)解法?

蒟蒻已经把度娘翻遍了,并没有很靠谱的结果

@dnbd 2020-09-17 00:05 回复 举报

最好是能提供一下代码,因为二分这个东西……比较玄学

@jeffqi 2020-09-17 00:08 回复 举报

有个很蠢的做法,你将每个点的权值赋为其相反数后直接套用最长上升子序列的模板,最后再将权值变回原样就行了。

@logwzc  2020-09-17 07:03 回复 举报

数组反过来,下降变上升

最长上升ans数组记录的是这个答案下的最小高度,那么最长下降就记录这个答案下的最大高度,然后就可以照旧二分了

@_虹_  2020-09-17 07:54 回复 举报

把数组反过来下降不就变成上升了

这个下降和上升不是完全一样的吗。。。。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。