Wooden Sticks (UVa Live Archive Asia - Site 4 (Korea) - 2001/2002 Taejon (Korea))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2322

問題

木の棒がn本存在する。木には長さlと重さwが存在する。この木を整形する機械があるのだが、機械の準備をするために1分かかってしまう。しかし、直前に整形した木よりも長さも重さも同じ以上の木を整形する場合は準備する時間は必要ない。全ての木を整形するためには何分掛かるか。
1<=n<=5000
1<=l,w<=10000

解法

同じ長さと重さを持つ木は一つにしてからl,wの順でソートする。次にdp[10001]を考える。このdpの初期値は0で各木を見る際にdp[w]=max(dp[w], max(dp[w〜10000] + 1))で更新する。最終的にこのdpで出てくる最大値が答え。dp[w〜10000]の最大値をセグメントツリーとかを使って計算すればO(n(logn+logw))になる。