• 欢迎光临~

LIS之nlogn做法

开发技术 开发技术 2022-12-25 次浏览

一.LIS

题目传送门
给定一个长为 (n) 的序列 (a_i),求这个序列的最长单调上升子序列长度。
(1)(a_i)(n)(10^5)

二.解析

(n^2)解法在此不再赘述,显然此方法过不了此题,下面考虑(nlogn)解法即二分
定义(f[n])为长度为(n)的子序列的最后一项的数值,(len)为当前的最优解,不难发现(f[n])是单调递增的
对于当前处理的元素(a[i]),分为两种情况
1.(a[i]>f[len]),此时自然可以直接将(a[i])接在(len+1)处,且更新(f[len+1]),即(f[++len]=a[i];)
2.(a[i]<=f[len]),此时无法形成(len+1)长的上升子序列,但我们要考虑将短于(len)的之前存储过的上升子序列的末项变得更小,这样才更有机会以后向这个序列后接入更多的数。(f[n])是单调的,考虑二分,找到最小的(f[k]>=a[i])(a[i])更新(f[k])。就是找到一个(f[k]),我们可以想象它所代表的一串上升子序列,将末项改小后,仍然使此上升子序列合法。其实,(f[k])都是由(f[k-1])继承而来的,所以(f[k-1])即我们想象里的长度为k的上升子序列的倒数第二项,所以只要将(a[i]>f[k-1])同时(a[i]<=f[k])修改就一定合法。又因为当(f[k])较小时,我们会发现这总归不如修改(f[b] (b>k))来的好,因为末项修改后大家都一样,即以后能装下更多数的潜力是一样的,那么就是当前长度越长越优,并且在以后的使上升子序列变长的过程中,是从最优方案为基础的,不是最优的那些方案也不必修改了。受此二者限制,我们只需找到最小的(f[k]>=a[i])并加以修改即可。此处建议读者手动模拟,深刻理解。

三.AC代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n,a[100001],f[100001],dp[100001];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=0x7fffffff;
    }
    f[1]=a[1];
    int len=1;
    for(int i=2;i<=n;i++)
    {
        int l=0,r=len,mid;
        if(a[i]>f[len])f[++len]=a[i];
        else 
        {
        while(l<r)
        {   
            mid=(l+r)/2;
            if(f[mid]>=a[i])r=mid;
            else l=mid+1; 
        }
        f[l]=min(a[i],f[l]);
        }
    }
    cout<<len<<endl;
	return 0;
}
程序员灯塔
转载请注明原文链接:LIS之nlogn做法
喜欢 (0)