首页 > 代码库 > [dp]最长单调递增子序列
[dp]最长单调递增子序列
https://www.51nod.com/tutorial/course.html#!courseId=12
解题关键：
如果将子序列按照长度由短到长排列，将他们的最大元素放在一起，形成新序列B{b1,b2,……bj}，则序列B满足b1 < b2 < …… <bj。这个关系比较容易说明，假设bxy表示序列A中长度为x的递增序列中的第y个元素，显然，如果在序列B中存在元素bmm > bnn，且m < n则说明子序列Bn的最大元素小于Bm的最大元素，因为序列是严格递增的，所以在递增序列Bn中存在元素bnm < bnn，且从bn0到bnm形成了一个新的长度为m的递增序列，因为bmm > bnn，所以bmm > bnm，这就说明在序列B中还存在一个长度为m，最大元素为bnm < bmm的递增子序列，这与序列的定义，bmm是所有长度为m的递增序列中第m个元素最小的序列不符，所以序列B中的各元素严格递增。
注意liss存的是下标，主要是为了求pre用，若只求max，你当然可以设成值。
1、只求数量模板
(1)liss为索引模板
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<iostream> 6 using namespace std; 7 typedef long long ll; 8 int arr[50002],liss[50002]; 9 int find1(int i,int l,int r){10 int mid;11 while(l<r){12 mid=(l+r)>>1;13 if(arr[liss[mid]]>arr[i]) r=mid;14 else l=mid+1;15 }16 return r;17 }18 int lis(int len){19 int max=1;20 liss[0]=0;21 for(int i=0;i<len;i++){22 int index=find1(i,0, max-1);23 if(index==max-1&&arr[liss[index]]<arr[i]){24 liss[max++]=i;25 continue;26 }27 liss[index]=i;28 }29 return max;30 }31 int main(){32 int n;33 cin>>n;34 for(int i=0;i<n;i++){35 cin>>arr[i];36 }37 ll ans=lis(n);38 printf("%lld\n",ans);39 return 0;40 }
(2)liss为值模板
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<iostream> 6 using namespace std; 7 typedef long long ll; 8 int arr[50002],liss[50002]; 9 int find1(int i,int l,int r){10 int mid;11 while(l<r){12 mid=(l+r)>>1;13 if(liss[mid]>arr[i]) r=mid;14 else l=mid+1;15 }16 return r;17 }18 int lis(int len){19 int max=1;20 liss[0]=0;21 for(int i=0;i<len;i++){22 int index=find1(i,0, max-1);23 if(index==max-1&&liss[index]<arr[i]){24 liss[max++]=arr[i];25 continue;26 }27 liss[index]=arr[i];28 }29 return max;30 }31 int main(){32 int n;33 cin>>n;34 for(int i=0;i<n;i++){35 cin>>arr[i];36 }37 ll ans=lis(n);38 printf("%lld\n",ans);39 return 0;40 }
2、带路径模板
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<iostream> 6 using namespace std; 7 typedef long long ll; 8 int arr[50002],liss[50002],pre[50002],res[50002]; 9 int find1(int i,int l,int r){10 int mid;11 while(l<r){12 mid=(l+r)>>1;13 if(arr[liss[mid]]>arr[i]) r=mid;14 else l=mid+1;15 }16 return r;17 }18 int lis(int len){19 int max=1;20 liss[0]=0;21 for(int i=0;i<len;i++){22 int index=find1(i,0, max-1);23 if(index==0&&arr[liss[index]]>=arr[i]){24 liss[index]=i;25 continue;26 }//增加这条语句主要是pre的影响，不需要路径的话，完全可以去掉。27 if(index==max-1&&arr[liss[index]]<arr[i]){28 liss[max++]=i;29 pre[i]=liss[index];30 continue;31 }32 liss[index]=i;33 pre[i]=liss[index-1];34 }35 36 int k=liss[max-1],t=max-1;37 while(pre[k]!=k){38 res[t--]=arr[k];39 k=pre[k];40 }41 res[t]=arr[k];42 return max;43 }44 int main(){45 int n;46 cin>>n;47 for(int i=0;i<n+2;i++){48 pre[i]=i;49 }50 for(int i=0;i<n;i++){51 cin>>arr[i];52 }53 ll ans=lis(n);54 printf("%lld\n",ans);55 for(int i=0;i<ans;i++){56 printf("%d ",res[i]);57 }58 printf("\n");59 }
[dp]最长单调递增子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。