2188 最长上升子序列
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 钻石 Diamond
题目描述 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
分类标签 Tags
动态规划
/*
预处理一下.
把没有贡献的值都删掉.
然后能够保证询问的位置在LCS里.
然后我们把问题推广一下.
如果有多个询问位置.
我们就先保证[k1,k2]位置间的任意数x,
使得x满足a[k1]<x<a[k2].
然后二分查找跑LCS就好了.
这里还是用lower_bound().
懒-_-
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 200001
using namespace std;
int n,k,a[MAXN],s[MAXN],tot,ans,c[MAXN];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void slove()
{
//ans=1;
for(int i=1;i<=tot;i++)
{
if(s[i]>c[ans]) c[++ans]=s[i];
else {
int p=lower_bound(c+1,c+ans+1,s[i])-c;
c[p]=s[i];
}
}
}
int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<k;i++)
if(a[i]<a[k]) s[++tot]=a[i];
s[++tot]=a[k];
for(int i=k;i<=n;i++) if(a[i]>a[k]) s[++tot]=a[i];
slove();
printf("%d",ans);
return 0;
}