【报资讯】浅谈 LIS 问题的几种做法

2023-04-29 15:15:20 来源：博客园

LIS 问题也就是最长不下降子序列问题，是一个经典的问题。

(资料图片仅供参考)

做法一

我们发现可以动态规划，设 \(f_i\) 表示前 \(i\) 项包含 \(i\) 的 LIS 长度。

有转移方程：

\[f_i=\max_{a_j\leq a_i} f_j +1\]

可以用 \(O(n^2)\) 的时间复杂度求解

做法二

有一个经典的 \(O(n \log n)\) 求解 LIS 的算法，本质可能类似贪心？

我们设 \(f_i\) 表示长度为 \(i\) 的 LIS 末尾最小为多少。

那么显然，这个 \(f_i\) 具有单调性，可以用二分维护。

具体实现我就不给了，这个不是我们的重点。

做法三

我们都知道经典的 \(O(n \log n)\) 求解 LIS 需要写一个很烦的二分，但是树状数组就不用啦。

观察动态规划转移方程：

\[f_i=\max_{a_j\leq a_i} f_j +1\]

注意到这就是一个二维偏序问题，所以树状数组轻松解决，对于我这种数据结构爱好者简直是福音。

#include#define LL long longusing namespace std;const LL N=1e5+5;LL n,a[N],t[N],f[N],mx;LL lowbit(LL x){return x&-x;}LL query(LL x){LL ans=0;while(x){ans=max(ans,t[x]);x-=lowbit(x);}return ans;}void update(LL x,LL y){while(x<=n){t[x]=max(t[x],y);x+=lowbit(x);}}int main(){scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}for(int i=1;i<=n;i++){f[i]=query(a[i])+1;update(a[i],f[i]); mx=max(f[i],mx);}printf("%lld",mx);}

关键词：