首页 > 代码库 > codevs 2188 最长上升子序列
codevs 2188 最长上升子序列
题目描述 Description
LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列，你还能解决吗？
给出一个长度为N整数序列，请求出它的包含第K个元素的最长上升子序列。
例如：对于长度为6的序列<2,7,3,4,8,5>，它的最长上升子序列为<2,3,4,5>，但如果限制一定要包含第2个元素，那么满足此要求的最长上升子序列就只能是<2,7,8>了。
输入描述 Input Description
第一行为两个整数N,K，如上所述。
接下来是N个整数，描述一个序列。
输出描述 Output Description
请输出两个整数，即包含第K个元素的最长上升子序列长度。
样例输入 Sample Input
8 6
65 158 170 299 300 155 207 389
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
80%的数据，满足0<n<=1000，0<k<=n
100%的数据，满足0<n<=200000，0<k<=n
传送门直达目的地
题解：清北第二套题的第二道题考试的时候写炸了，这引起我的反思，要复习一下最长上升子序列。然后就找了个最长上升子序列的题。这道题增加的一点难度是必须含有第k个元素。稍微进行一下修改即可。
当查找的第k个元素时，由于必须包含k，所以k插入位置x即为此时找到的最长上升子序列的长度。因为f数组中f[x]以后的数都是在k之前出现的比k大的数。此是f[1]~f[x]为一固定的序列，不再发生变化。然后a数组往后查找时，若有比a[k]小的数，直接忽略不进行运算。就避免了f[1]~f[k]序列中的数发生变化。
#include<cstdio>#include<iostream>#define N 200100using namespace std;int n,k,len=1,l=0;int a[N];int f[N];int erfen(int l,int r,int p){ if (l>r) return l; int mid=(l+r)>>1; if (f[mid]<p) erfen(mid+1,r,p); else erfen(l,mid-1,p);}int main(){ scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%d",&a[i]); f[len]=a[1]; for (int i=2;i<=n;i++) { if (i>k&&a[i]<a[k]) continue;//忽略比a[k]小的数 int bj; if (a[i]>f[len]) f[++len]=a[i],bj=len; else bj=erfen(l,len,a[i]); if (bj>len) len=bj; f[bj]=a[i]; if (i==k) l=len=bj;//长度进行更改 } printf("%d",len); return 0;}
codevs 2188 最长上升子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。