1288.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 32 行

/*  This Code is Submitted by wywcgs for Problem 1288 on 2005-12-03 at 00:41:55 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 65536;

int main()
{
	int t, T, n, i;
	int bridge, upper[MAX];
	int len;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		len = 0;
		for(i = 0; i < n; i++) {
			scanf("%d", &bridge);
			int *up = upper_bound(upper, upper+len, bridge);
			if(up - upper >= len) {
				upper[len++] = bridge;
			} else if(*up > bridge) {
				*up = bridge;
			}
		}
		printf("%d\n", len);
	}
	
	return 0;
}