POJ(PKU) 1631 Bridging signals

解法：最長増加部分列(LIS)

蟻ゲーです。

#include <cstdio>
#include <algorithm>

const int INF = 100000000;

using namespace std;

int main(){
  
  int n;
  scanf("%d",&n);
  
  while(n--){
  
  int p;
  int d[40003]={0};
  
  int dp[40003] = {0};
  
  scanf("%d",&p);
  
  for(int i = 0;i < p;i++){
    scanf("%d",&d[i]);
  }
  
  fill(dp, dp + p, INF);
  
  for(int i = 0;i < p;i++){
    *lower_bound(dp,dp + p, d[i]) = d[i];
  }
  
  
  printf("%d\n",lower_bound(dp, dp + p, INF) - dp);
  
  }
  
  return 0;
  
}