1631.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int a[40000], n;
int ans[40000];
int id[40000], m;

bool cmp( int s1,int s2 )
{
	return a[s1] < a[s2];
}

int main()
{
	int i, j, s;
	int cas;

	scanf( "%d", &cas );
	while( cas-- )
	{
		scanf( "%d", &n );
		for( i=0; i<n; i++ )
			scanf( "%d", &a[i] );

		ans[0] = 1; id[0] = 0;
		for( i=1, m=1; i<n; i++ )
		{
			if( a[ id[m-1] ] < a[i] )
			{
				id[m] = i;
				ans[i] = ans[ id[m-1] ] + 1;
				m++;
			}
			else
			{
				j = lower_bound( id, id+m, i, cmp ) - id;
				ans[i] = ans[ id[j] ];
				id[j] = i;
			}
		}

		printf( "%d\n", ans[ id[m-1] ] );
	}

	return 0;
}