【题目描述】 LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列，你还能解决吗？ 给出一个长度为N整数序列，请求出它的包含第K个元素的最长上升子序列。 例如：对于长度为6的序列<2,7,3,4,8,5>，它的最长上升子序列为<2,3,4,5>，但如果限制一定要包含第2个元素，那么满足此要求的最长上升子序列就只能是<2,7,8>了。 【输入格式】 第一行为两个整数N,K，如上所述。 接下来是N个整数，描述一个序列。 【输出格式】 请输出两个整数，即包含第K个元素的最长上升子序列长度。 【样例输入】 8 6 65 158 170 299 300 155 207 389 【样例输出】 4 【数据范围】 1<=n<=200000，1<=k<=n 【分析】 首先要把a数组中肯定不满足条件的，即1<=i<=k-1中若a[i]>a[k]就删除a[i]，k+1<=i<=n中若a[i]<=a[k]就删除a[i]。 设f[i]表示以第i个数结尾的最长上升子序列长度，s[i]表示长度为i时最靠左的上升子序列的终点值（注意不是序号）。 举个实例： a 10 13 11…… 计算s[2]时，发现有10-13,10-11两个长度相同的上升子序列，这时我们选择哪个呢？为了“让后人乘凉”，于是“前人”就需要“栽树”，把10-13删除，因为如果下一个数是12，10-13就不是最优了，这也是N^2级动规的不足：有些明显不是最优解的解应该剪枝。 不难发现s数组是单调的，也就是上升的。 然后看s数组的求法。 设e为s数组的终点指针，若s[e]<=a[i]，就是说a[i]可以插在s[e]后面，于是可以使用二分法找到s[e]。 此时可以发现，f[i]=e+1,d[f[i]]=a[i].
var a,f,s:array[0..200001]of longint; i,n,k,len,l,r,mid,e:longint; begin readln(n,k); for i:=1 to n do read(a[i]); s[1]:=a[1]; f[1]:=1; len:=1; for i:=2 to n do begin if (i<k)and(a[i]>=a[k]) then continue; if (i>k)and(a[i]<=a[k]) then continue; e:=0; l:=1;r:=len; while l<=r do begin mid:=(l+r) div 2; if s[mid]<a[i] then begin l:=mid+1; e:=mid; end else r:=mid-1; end; f[i]:=e+1; if f[i]>len then len:=f[i]; s[f[i]]:=a[i]; end; write(len); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533518.html
