UVa 481 - What Goes Up

题目：最大上升子序列。

分析：dp、lis、二分、单调队列。LIS的O(nlogn)算法。此算法，利用单调队列+二分优化。单调队列里的元素Q[i]为，到目前为止、长度为i的LIS中最小的结束元素。运行过程中，如果当前元素小于队尾元素，则可以和前面的构成LIS，直接加入队尾，否则替换之前的长度相同的LIS的结尾元素，使对应位置上的元素变小，由于队列满足单调性，所以利用二分查找提高效率。例如：序列为：{1，3，2，3}，则计算过程Q为：{1}，{1，3}，{1，2}，{1，2，3}。这样做是因为，如果{1,3}可以构成LIS的前缀串，那么{1,2}必然可以构成LIS的前缀传，并且可以接纳更多的后缀。 www.zzzyk.com

注意：数据规模较大O(n^2)算易做图TLE、求的是最后的LIS利用单调队列直接满足。

[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int data[ 100000 ];
int length[ 100000 ];
int front[ 100000 ];
int Q[ 100000 ];

void output( int v )
{
    if ( front[v] )
        output( front[v] );
    printf("%d\n",data[v]);
}

int bs( int r, int v )
{
    int l = 1;
    while ( l < r ) {
        int mid = (l+r)>>1;
        if ( data[Q[mid]] < v )
            l = mid+1;
        else r = mid;
    }
    return r;
}

int main()
{
    int count = 1;
    while ( scanf("%d",&data[count]) != EOF )
        count ++;

    int tail = 0;
    Q[++ tail] = 1;
    for ( int i = 2 ; i < count ; ++ i )
        if ( data[Q[tail]] < data[i] ) {
            Q[++ tail] = i;
            front[i] = Q[tail-1];
        }else {
            int id = bs( tail, data[i] );
            Q[ id ] = i;
            front[i] = Q[id-1];
        }

    printf("%d\n-\n",tail);
    output( Q[tail] );
    return 0;
}

补充：软件开发 , C++ ,