zoj 1986 Bridging Signals

zoj 1986 Bridging Signals

#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define P40010#define hpmax(a,b)((a)>(b)?(a):(b))int D[P], map[P];int p;int find( int len, int value ){int i, j, mid;i = 1; j = len;while ( i <= j ) {mid = (i+j)>>1;if ( D[mid] > value ) j = mid-1;else if ( D[mid] < value )i = mid+1;else return mid;}return i;}int main(){int t, i, j, k;scanf("%d", &t );while ( t -- ) {scanf("%d", &p);for ( i = 1; i <= p; ++ i ) {scanf("%d", &map[i] );}D[1] = map[1];j = 1;for ( i = 2; i <= p; ++ i ) {if ( map[i] > D[j] ) {D[++j] = map[i];}else {k = find( j, map[i] );D[k] = map[i];}}printf("%dn", j );}return 0;}