算法描述》关于LIS的nlogn方法

　　上次TYVJ有一道裸LIS，然而我当时直接打了一个N^2暴力就草草了事，然后就ZZ了，只拿了60分，其实NlogN的LIS和N^2的差的不多，只是没有N^2，好想罢了，鉴于某学弟的要求，所以就重现一下金哥当年讲LIS的风范。

　　首先，LIS指的是最长上升子序列。指的是我们要求出一个在母序列中找出一些元素，在保证这个子序列上升的同时，保证这个序列是整个母序列里满足这一要求的最长序列。

　　那么我们可以直接这样想，我们要保证当前所拼接的链最大，那么对于每一个元素来说，可以直接一遍循环判断它能够属于哪一个链，使当前以这个元素为结尾的链所接的元素个数最多，也就是所得的结果越大。

　　那么对于一个元素ai，可以直接找a1到ai-1的元素中ai链在哪一个元素所得解最优，最优解放在f[i]里，这种对于所有情况的判断，很明显是DP，那么，转移方程就是：f[i]=a[j]<a[i]?max(f[j]+1,f[i]):f[i]

　　那么明显的，这是一个N^2的算法，对于每一个元素要求以前是否有能够找到更优解的上一步元素，一个判断N遍。

　　那如何得到一个更优算法捏？

　　其实很简单，让我们先回顾刚才我们所做的操作，我们对于当前的一个元素，找前面所算过的所有结果，试图找出更优解。我们在做这一工作时，也找了很多肯定不为最优解的元素，这是一件很浪费的事情，那么我们可以找一个优化这一过程的方法。

　　我们知道，对于任意一个元素，使它的解更优的方案肯定是a[i]小，并且f[i]大的一个理想元素，因为对于这样的一个理想元素，才可能使后面的解更优，而最大的f[i]是有限的，所以，我们很轻易得想到一个优化方法：

　　使用一个数组d，用d[i]记录当前 f[i] 为 i 的 a[i]最小的元素，d随着元素的向后递推逐渐维护。

　　开一个数组就能使LIS更优吗？答案是当然的，原因很简单，我们发现，我们所维护的这个d数组是递增的，这一结论可以通过反证法易证。既然这一数组是递增的，我们就可以轻易的通过二分来得到最优解。

　　所以，对于每一个元素做一遍二分，显而易见复杂度是nlogn的。

附上一道水题 codevs

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

 #include<stdio.h>

 int cnt,n,a[],best[];

 void push(int x)

 {

     int L=,R=cnt;

     int mid;

     while(L<=R)

     {

         mid=(L+R)/;

         if(x>best[mid]){

             L=mid+;

             if(best[L]>x)best[L]=x;

         }

         else R=mid-;

     }

 }

 int main()

 {

     int k,i;

     scanf("%d%d",&n,&k);k--;

     for(i=;i<=n-;i++)

         {

         scanf("%d",&a[i]);

         if(i>k&&a[i]<=a[k]){i--;n--;

         }

         }

     for(i=;i<=k-;i++)

     if(a[i]>=a[k])a[i]=;

     for(i=;i<=n-;i++)

         {

             if(a[i]<best[cnt]&&a[i])push(a[i]);

             else if(a[i])best[++cnt]=a[i];

             }

     printf("%d",cnt);

     return ;

 }

巴特西

算法描述》关于LIS的nlogn方法

最新文章

热门文章