1259:【例9.3】求最长不下降序列

2021/8/2 6:05:52

本文主要是介绍1259:【例9.3】求最长不下降序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

http://ybt.ssoier.cn:8088/problem_show.php?pid=1259

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll N=1e5+520;
 5 ll a[N],dp[N];
 6 const int INF=0x3f3f3f3f;
 7 ll n;
 8 int main()
 9 {
10     scanf("%lld",&n);
11     for(int i=0;i<n;i++)scanf("%lld",&a[i]);
12     ll len=0;
13     dp[0]=-INF; 
14     for(int i=0;i<n;i++)
15     {
16         ll l=0,r=len;
17         while(l<r)
18         {
19             ll mid=l+r+1>>1;
20             if(dp[mid]<=a[i]) l=mid;
21             else r=mid-1;
22         }
23         len=max(len,r+1);//如果可以更新子序列长度, 
24         dp[r+1]=a[i];//更新子序列//要么插在里面更优,要么插在外面延伸 
25     }
26     cout<<"max="<<len<<'\n';
27     for(int i=1;i<=len;i++) cout<<dp[i]<<(i==len?'\n':' ');
28     return 0;
29  } 
30 //关于最长上升子序列,第一种做法是这样的,对于当前结尾的,我对于前面结尾的,每一个扫一遍得到最长的。
31 //第二种方法是动态维护最长上升子序列,因为要的是最长子序列,那么贪心的,用最小的即可,那么每一次以xx结尾的,那么只要能够找到结尾点就插入,那么一定可以满足原来的子序列,并且能够使得该序列最优,更有可能延长。
32  

 



这篇关于1259:【例9.3】求最长不下降序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程