HDU 1950 Bridging signals （LIS，O(nlogn)）

题意：

　　给一个数字序列，要求找到LIS，输出其长度。

思路：

　　扫一遍+二分，复杂度O(nlogn)，空间复杂度O(n)。

　　具体方法：增加一个数组，用d[i]表示长度为 i 的递增子序列的最后一个元素，且该元素总是保持当前最小。初始化d[1]=A[i]，当前LIS的长度len=1。从 2 to n，若A[i]>d[len]，则d[++len]=A[i]，否则，在数组d中找到A[i]应该插入的位置，代替掉那个第一个比它大的数字，比如d[k]<A[i]<=d[k+1]，直接将A[i]代替掉d[k+1]。完成后len就是LIS的长度了。

 #include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <map>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 2147483647

 #define LL unsigned long long

 using namespace std;

 const double PI  = acos(-1.0);

 const int N=;

 const int mod=1e9+;

 int a[N], d[N];

 int* lower_( int *s,int *e,int val ) //二分找值，返回下标

 {

     int L=, R=e-s-, mid;

     while(L<R)

     {

         mid=R-(R-L+)/;            //保证至少减少1

         if( s[mid]<val )    L=mid+;//至少增加1

         else                R=mid;

     }

     return &s[R];

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int t, n, len;

     cin>>t;

     while(t--)

     {

         scanf("%d",&n);

         for(int i=; i<=n; i++) scanf("%d",&a[i]);

         len=;

         d[len]=a[];

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

         {

             if( a[i]>d[len] )    d[++len]=a[i];

             else                 *lower_(d+,d+len+,a[i])=a[i];

             //else               *lower_bound(d+1,d+len+1,a[i])=a[i]; 上一行代码可换成此行

         }

         printf("%d\n",len);

     }

     return ;

 }

AC代码

巴特西

HDU 1950 Bridging signals （LIS，O(nlogn)）

最新文章

热门文章