2013年9月27日 星期五

2013/9/27 UVA 11456 - Trainsorting

/* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2451 */
#include <iostream>
#include <cstdio>

using namespace std;

int train[4000]; int LIS[2000];

int main()
{
    int T;
    scanf("%d", &T);

    while( T-- )
    {

        int N;
        scanf("%d", &N);

        if( N==0){printf("0\n");continue; }

        for(int i = 0; i < N; i++)
        {
            scanf("%d", &train[N-1+i]);
            train[N-1-i] = train[N-1+i];
        }
      //  cout<<"XD\n";

        int lth = 1;
        LIS[0] = train[0];

        for(int i = 1; i < 2*N-1; i++)
        {
            if( train[i] <= LIS[0] )
                LIS[0] = train[i];
            else if( train[i] > LIS[lth-1] )
                LIS[lth++] = train[i];
            else
            {
                int l = 0; int r = lth-1; int mid;

                while( l+1 != r )
                {
                    mid = (l+r)/2;
                    if( train[i] > LIS[mid] )
                        l = mid;
                    else
                        r = mid;
                }
                LIS[r] = train[i];
            }
        }

        printf("%d\n", lth);
    }
}

沒有留言:

張貼留言