web analytics

Longest Increasing Subsequence LIS变式题

题目链接:https://ac.nowcoder.com/acm/contest/1110/E

认真读题发现关键点在于那个被扣掉的K,

那我们应该怎么处理掉这个被扣掉的K?\(n \leq 5000\)可以暗示我们\(O(n^2)\)的算法可以实现。

LIS除了平方算法还有个log算法, 那个以长度为下标的想法可以用到。

一开始先做一遍以i为最后值的LIS。之后我们用visit记录 i 长度的LIS的最后一个值是多少,当我们在判断K之后的数的时候

比如说我们 在判断第 j 个数(这个数在K之后)的F的时候 就可以用\( visit[F[j]-1] \)与 第j个数比较 如果 visit大了 说明我们删除掉的 K 对我们这个j的LIS有影响,不然第j个数的LIS就可以接在\(visit[F[j]-1] \)后面。所以删掉这个K会让我们的 以第j个数结尾的LIS少1.所以那个位置的LIS就是F[j]-1。然后每次往后枚举的时候 更新我们的visit。