首页 > 代码库 > 最长不下降子序列（LIS）

最长不下降子序列（LIS）

2024-07-15 07:29:46   224人阅读

最长上升子序列、最长不下降子序列，解法差不多，就一点等于不等于的差别，我这里说最长不下降子序列的。

有两种解法。

一种是DP，很容易想到，就这样：

1         REP(i,n)2         {3             f[i]=1;4             FOR(j,0,i-1)5                 if(a[j]<=a[i]) f[i]=max(f[i],f[j]+1);6         }

DP是O(n^2)的，我感觉已经不错了不过还有超碉的nlogn的方法。

nlogn的方法：

用栈和二分查找。

遇到一个元素a[i]，若它不小于栈顶s[top]，直接入栈；若大于栈顶，则在栈中二分查找，用它替换栈中比它大的第一个元素。最终栈的大小就是最长不下降子序列的长度（栈中元素并不一定是这个子序列，只有大小是一样的）

 

例题：http://acm.hdu.edu.cn/showproblem.php?pid=1950

DP代码（例题TLE）：

 1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<map> 8 #include<set> 9 using namespace std;10 #define ll __int6411 #define usint unsigned int12 #define mz(array) memset(array, 0, sizeof(array))13 #define minf(array) memset(array, inf, sizeof(array))14 #define REP(i,n) for(int i=0;i<(n);i++)15 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)16 #define RD(x) scanf("%d",&x)17 #define WN(x) printf("%d\n",x);18 #define RE  freopen("D.in","r",stdin)19 #define WE  freopen("1.out","w",stdout)20 21 const int maxn=44444;22 23 int a[maxn];24 int f[maxn];25 int main()26 {27     //RE;28     int t,n,i,j;29     int ans;30     RD(t);31     while(t--)32     {33         RD(n);34         ans=0;35         REP(i,n)36             RD(a[i]);37         REP(i,n)38         {39             f[i]=1;40             FOR(j,0,i-1)41                 if(a[j]<=a[i]) f[i]=max(f[i],f[j]+1);42             if(f[i]>ans)ans=f[i];43         }44         WN(ans);45     }46     return 0;47 }
View Code

 

nlogn代码：

 1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<map> 8 #include<set> 9 #include<stack>10 using namespace std;11 #define ll __int6412 #define usint unsigned int13 #define mz(array) memset(array, 0, sizeof(array))14 #define minf(array) memset(array, inf, sizeof(array))15 #define REP(i,n) for(int i=0;i<(n);i++)16 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)17 #define RD(x) scanf("%d",&x)18 #define WN(x) printf("%d\n",x);19 #define RE  freopen("D.in","r",stdin)20 #define WE  freopen("1.out","w",stdout)21 22 const int maxn=44444;23 24 int a[maxn];25 int s[maxn],sn;26 int main() {27     //RE;28     int t,n,i,j;29     int l,r,mid;30     int ans;31     RD(t);32     while(t--) {33         RD(n);34         ans=0;35         REP(i,n)36             RD(a[i]);37         sn=1;38         s[0]=a[0];39         FOR(i,1,n-1) {40             if(s[sn-1]<=a[i]) s[sn++]=a[i];41             else {42                 l=0;43                 r=sn-1;///二分找比a[i]大的第一个（s[sn-1]肯定比a[i]大，l不会加爆）44                 while(l<=r) {45                     mid=(l+r)>>1;46                     if(s[mid]>a[i]) r=mid-1;47                     else l=mid+1;48                 }49                 s[l]=a[i];50             }51         }52         WN(sn);53     }54     return 0;55 }
View Code

 


联系
我们