P3902 递增 – Xhesica's blog

链接：P3902

-----------------------------------------

这道题就是最长上升子序列的模板题，因为我们修改的时候可没说不能改成小数（暴力）

最长上升子序列有很多求法，这道题dp是不行的，TLE。

就要用nlogn的二分算法

这个算法是这样的，建立一个数组了，low，其中low[i]表示长度为i的上升子序列的结尾最小值

来考虑维护它，如果一个新数a[i]比low[最后一个]大，我们就low[++low的长度]=a[i]；

else，考虑一下，如果结尾的元素越小，他的潜力就越大，所以贪心的考虑一下，为什么不让它去给low增加点潜力呢？

找到第一个大于等于a[i]的low，并且更新它。

这样就可以在nlogn内求出了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100005;
const int inf=0x7f7f7f7f;
int n,ans;
long long  low[maxn],a[maxn];
int main(){

    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        low[i]=inf;
    }
    low[1]=a[1];
    ans=1;
    for(int i=2;i<=n;++i){
        if(a[i]>low[ans])
        low[++ans]=a[i];
        else
        low[lower_bound(low+1,low+ans+1,a[i])-low]=a[i];
    }
    cout<<n-ans;
    return 0;
}

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论