[最长非升子序列]北大 POJ 1887 Testing the CATCHER - c++编程基础

[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
#include
#include
#include
#include

#include
#include
#include
#include
#include

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