首页 > 代码库 > TYVJ1254

TYVJ1254

2024-07-19 16:31:58   213人阅读

最长不降子序列，O（n^2）算法能超时超到明年
需要o(nlogn)算法（CMI）
这个问题利用到了辅助数组d[i]，这里姑且称它为栈，因为对该
数组的操作像是栈的操作,d[i]表示长度为i的不降子序列中最小
的最后元素，最后栈的长度就是最长不降子序列的长度

当循环到a[i]的时候和栈顶元素s比较，如果s<=a[i]，就是说a
[i]比最长的不降子序列的最小的那个元素大或等于，那么把a
[i]放到栈顶，子序列也就加了1

如果s>a[i]则在栈中找最大的j使得d[j]<=a[i],然后将j+1替换
为a[i]，因为栈中的元素都是单调递增的(随便想一下就知道)，
所以可以用二分求上限求得，这样的查找的时间复杂度就是
o(logn),总的复杂度就是o(nlogn)
重点就是二分求上限，LRJ的小白书上就有

 

 

 1 //288 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 const int maxn = 30005; 8 int d[maxn],a[maxn],cnt = 0; 9 int up_search(int l,int r,int val)10 {11     while(l<r)12     {13         int m = (l+r)>>1;14         if(d[m]<=val)l = m+1;15         else r = m;16         //printf("%d\n",cnt++);17     }18     return l;19 }20 int main()21 {22     //freopen("in.txt","r",stdin);23     int n;24     cin>>n;25     for(int i = 1;i<=n;++i)scanf("%d",a+i);26     int r = 0;27     for(int i = 1;i<=n;++i)28         if(!r)d[++r] = a[i];29         else30         {31             if(a[i]>=d[r])d[++r] = a[i];32             else d[up_search(1,r,a[i])] = a[i];33         }34     printf("%d\n",r);35     return 0;36 }

 

TYVJ1254


联系
我们