POJ 1631 Bridging signals

問題

解法
最長増加部分列(LIS)をとけばよい
spaghetti source みてLISをO(n log n)で解くアルゴリズムをみた

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1 << 29;
const int MAX_P = 40000;
int T, P;
int a[MAX_P];
int solve_lis(){
	int lis[P + 1];
	fill(lis, lis + P + 1, INF);
	lis[0] = 0;
	for(int i = 0; i < P; i++){
		int p = lower_bound(lis, lis + P + 1, a[i]) - lis;
		lis[p] = a[i];
	}
	int ret = 0;
	for(ret = 0; ret < P + 1; ret++){
		if(lis[ret] == INF)
			break;
	}
	return ret;
}
int main(){
	scanf("%d", &T);
	for(int t = 0; t < T; t++){
		scanf("%d", &P);
		for(int i = 0; i < P; i++)
			scanf("%d", &a[i]);
		printf("%d\n", solve_lis() - 1);
	}
	return 0;
}