[最長非升子序列]北大 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.2cto.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