包含限定项LIS

【题目描述】
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.

包含限定项LIS

推荐阅读