BZOJ 3173: [Tjoi2013]最长上升子序列 splay dp 思维题

我们发现他按照从小到大插入,如果我插入一个值,那可能会影响非常多的上升子序列。但是如果我们反着来,每次删除一个最大的,我们只影响以他为结尾的子序列,相对而言就容易处理多了。所以我们先用平衡树,求出最终序列。

然后我们考虑常规的nlogn最长上升子序列做法,我们可以边做dp,边维护出,保持一个长度为l的最长上升子序列所需要的最小元素。然后就得出答案了~

发表评论