[最长非升子序列]北大 POJ 1887 Testing the CATCHER

[cpp]
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.

    URL   : http://poj.org/problem?id=1887
    Name : 1887 Testing the CATCHER
    Classification : 最长非升子序列

    Date : Wednesday, July 11, 2012
    Time Stage : half an hour

    Result:
10420937    panyanyany
1887
Accepted    224K    16MS    C++
1692B   2012-07-11 09:59:34
10420935    panyanyany
1887
Accepted    224K    16MS    C++
1692B   2012-07-11 09:59:09
10420931    panyanyany
1887
Runtime Error           C++
1691B   2012-07-11 09:58:54
10420923    panyanyany
1887
Accepted    340K    0MS C++
1692B   2012-07-11 09:58:22

Test Data :

Review :
数组开到40005，用时0MS，减少到10005的时候，用时却是16MS……郁闷，求解释……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>

using namespace std ;

#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value
#define max(x, y)        ((x) > (y) ? (x) : (y))
#define min(x, y)        ((x) < (y) ? (x) : (y))

#define INF     (0x3f3f3f3f)
#define MAXN    (1005)

#define L(x)    ((x)<<1)
#define R(x)    (((x)<<1)|1)
#define M(x, y) (((x)+(y)) >> 1)

#define DB    //

int a[MAXN], order[MAXN];

int LNotIncS(int a[], int n)
{
    int i, len, r, l, m;
    MEM(order, 0);
    len = 1;
    for (i = 0; i < n; ++i)
    {
        l = 1;
        r = len;

        while (l <= r)
        {
            m = (l + r) >> 1;
            if (order[m] >= a[i])
                l = m + 1;
            else
                r = m - 1;
        }

        if (order[l] < a[i])
            order[l] = a[i];

        if (len < l)
            len = l;
    }
    return len;   www.zzzyk.com
}

int main()
{
    int x, n, tc;
    n = 0;
    tc = 1;
    while (scanf("%d", &x))
    {
        if (0 == n && x == -1)
            break;

        if (x != -1)
        {
            a[n++] = x;
        }
        else
        {
            if (tc != 1)
                putchar('\n');
            printf("Test #%d:\n", tc++);
            printf(" maximum possible interceptions: %d\n", LNotIncS(a, n));
            n = 0;
        }
    }
    return 0;
}

作者：panyanyany

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