AOJ DPL1_D - Longest Increasing Subsequence

・問題
Longest Increasing Subsequence | Aizu Online Judge

特にいうこともない。解説は蟻本とこれ(http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=DPL_1_D)に投げる。
fillとlower_boundめっちゃ便利。(両方algorithm)

・実装(C++)

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

int main(){
	int n, a[100000];
	//input
	scanf(" %d", &n);
	for(int i=0; i<n; ++i) scanf(" %d", &a[i]);
	
	const int INF = 1e9+1;
	//dp[i]:=長さがi+1であるような増加部分列における最終要素の最小値
	int dp[100000];
	//initialize
	fill(dp, dp+n, INF);
	for(int i=0; i<n; ++i){
		*lower_bound(dp, dp+n, a[i]) = a[i];
	}
	
	printf("%d\n", lower_bound(dp, dp+n, INF)-dp);
}