No.038 D

箱は $h_i$ で昇順にソートしておく.

$i$ 番目の箱を一番外側の箱にしたときの最大の入れ子の数を $A(i)$ とすると,

$$A(i) = \max\{ A(j) \vert j \lt i,\ w_j \lt w_i \} + 1$$

となる. これをこのまま計算すると $O(N^2)$ となる.

そこでセグメント木を使う. インデックスとして $w_i$ を取り, 値としてそのときの最大の入れ子の数として DP を行いつつセグメント木を更新していく.

$h_i$ が同じ値がある場合は $w_i$ で降順になるようにソートしておけば同じ $h_i$ の後の DP が前の DP に影響を受けることがなくなる.