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; }