首页 > 代码库 > 【noi 2.6_1759】最长上升子序列（DP+优化）
【noi 2.6_1759】最长上升子序列（DP+优化）
有2种解法：
1.O（n^2） f[i]定义为必选a[i]的答案。
2.O（n log n) 保存扫完前i个选出的答案序列，不断扩大和更新（同位存尽量小的数）这个序列。
代码1——
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=1010; 8 int a[N],f[N]; 9 10 int mmax(int x,int y) {return x>y?x:y;}11 int main()12 {13 int n,ans=0;14 scanf("%d",&n);15 for (int i=1;i<=n;i++) scanf("%d",&a[i]);16 for (int i=1;i<=n;i++)17 {18 f[i]=1;19 for (int j=1;j<i;j++)20 if (a[i]>a[j]) f[i]=mmax(f[i],f[j]+1);21 ans=mmax(ans,f[i]);22 }23 printf("%d",ans);24 return 0;25 }
代码2——
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=1010; 8 int a[N],f[N]; 9 10 int ffind(int l,int r,int x)11 {12 if (l==r) return l;13 int mid=(l+r)>>1;14 if (x>f[mid]) return ffind(mid+1,r,x);15 else return ffind(l,mid,x);16 }17 int main()18 {19 int n,ans=0;20 scanf("%d",&n);21 for (int i=1;i<=n;i++) scanf("%d",&a[i]);22 f[++ans]=a[1];23 for (int i=2;i<=n;i++)24 {25 int x;26 if (a[i]>f[ans]) x=++ans;27 else x=ffind(1,ans,a[i]);28 f[x]=a[i];29 }30 printf("%d",ans);31 return 0;32 }
【noi 2.6_1759】最长上升子序列（DP+优化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。