【基础练习】【二分】codevs2188 最长上升子序列(限定元素)题解

浅浅的花香味﹌ 2022-08-09 05:24 169阅读 0赞

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

数据范围及提示 Data Size & Hint

80%的数据，满足0<n<=1000，0<k<=n

100%的数据，满足0<n<=200000，0<k<=n

这道题目其实和前面两道二分也差不多，那么如何做到保证有k呢？只要把k前面比他大的都删除（赋值为极大值），把它后面比他小的都删除（读入时跳过）即可。

对于k前面比它大的为何赋值为极大值是可行的，我们可以这样理解：

由于k前方有一个极大值，他后面必然不能再接任何数字，也就是说，这个极大值必定是他所属的序列中最后一个数字。

如果k是最后一个数字，那么取k和取极大值的序列长度在最坏情况下也是相同的。这里的最坏情况指k前面就是一个极大值。而如果k前面不是极大值，那么k结尾的LIS一定大于等于（很大可能是大于）以极大值结尾的LIS长度。

如果k不是最后一个数字，那么显然由于这个极大值在k前方，而k后方可能还会有能接的数字，极大值结尾一定不会比含kLIS更优。

这个证明显然是不充分不严谨的，然而足以让我们理解到此算法的正确性。

如有大神做严禁论证，欢迎在评论中提出。

放代码

//codevs2188 ×î³¤ÉÏÉý×ÓÐòÁÐ£¨ÏÞ¶¨ÔªËØ£©
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=200000+10;
    const int oo=0x3f3f3f3f;
    int n,k,p;
    int a[maxn];
    int f[maxn];
    
    int find(int x)//Ä¿±ê£ºÕÒ³öµ±Ç°ÐòÁÐÖÐ±Èx´óµÄµÚÒ»¸öÊýµÄÎ»ÖÃ 
    {
        int l=1,r=p;
        while (l
          
           =x) r=mid;
            else l=mid+1;
        }
        return l;
    }
    
    
    int main()
    {
        int x;
        scanf("%d%d",&n,&k);
        int it=0,cnt=k+1;
        for (int i=1;i
           
            a[k]) a[i]=oo; for (int i=k+1;i<=n;i++) { scanf("%d",&x); if (x>a[k]) a[cnt++]=x; else continue; } p=1;//pointer f[1]=a[1]; for (int i=2;i<=n;i++) { if (a[i]>f[p]) { f[++p]=a[i]; } else { int pos=find(a[i]); f[pos]=a[i]; } } printf("%d",p); }

——浮云一别后，流水十年间