Codeforces #198 Div1. B. Bubble Sort Graph

これはライブラリ問題…。
http://codeforces.com/contest/341/problem/B

問題

1～Nのpermutationである数列Aが与えられる。
ここで、同様に1～N番の点を持つグラフGを考える。

数列Aに対してバブルソートを行いAを昇順にするが、その際A[i]>A[i+1]でこの２要素をswapした場合、グラフG上で(swap前に)A[i]番の点からA[i+1]番の点に有向辺を張る。
バブルソート終了後、最大独立集合の点の数を答えよ。

解法

数列A上で昇順に並んでいる数値間では辺は張られない。
よって、数列A上で最長の部分増加列を探せばよい。

…これってLISだよね。ということでLISを求めるだけ。
自分はライブラリを持ってなかったので、本番ネットやら蟻本でLIS書いて解答。

int N;
vector<int> A;

void solve() {
	int f,r,i,j,k,l, x,y,y2;
	
	cin>>N;
	FOR(i,N) A.push_back(GETi()-1);
	
	vector<int> AA(N,N+1);
	vector<int> ID(N);
	FOR(i,N) {
		vector<int>::iterator it=lower_bound(AA.begin(), AA.end(), A[i]);
		ID[i]=distance(AA.begin(), it);
		AA[ID[i]]=A[i];
	}
	
	_P("%d\n",1+*max_element(ID.begin(),ID.end()));
	return;
}

まとめ

この後別のCodeforcesの回でもLISが出てきたので、ライブラリ化した。