POJ-1065, ZOJ-1025, LiveArchive-2322, TJU-1469 : Wooden Sticks

問題概要

数字のペアの列(長さN<5000)が与えられる。x≦x', y≦y'のとき(x,y)と(x',y')の間に順序を入れる。このグラフでの最小パス被覆の本数を求める問題。

解説

某所で日本語解説を見てしまっていたので殆ど自分で考えずに解いてしまった。
Dilworthの定理より、最小パス被覆を求める代わりに最大反鎖のサイズを求める。これはペアをソートした後第二要素の最長狭義減少列を求めればよい。

acceptされたコード

計算量O(N*log N)。

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

const int MAX_N = 5000;
const int INF = 1<<29;

int N;
pair<int,int> as[MAX_N];
int dp[MAX_N];

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		scanf("%d%d", &as[i].first, &as[i].second);
	}
}

int solve(){
	sort(as, as + N);
	N = unique(as, as + N) - as;
	fill(dp, dp + N, INF);

	for(int i=0; i<N; i++){
		as[i].second *= -1;
		*lower_bound(dp, dp + N, as[i].second) = as[i].second;
	}
	return lower_bound(dp, dp + N, INF) - dp;
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("%d\n", solve());
	}

	return 0;
}