オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 038 D: プレゼント

問題文

abc038.contest.atcoder.jp

解法

dp[i] := i 番目の箱を最も外側に使う時の最大の入れ子の数 でDPする。しかし、普通にやると、その箱に入る箱を探すのを含めて $O(N^2)$ になってしまう。

DPの遷移は、dp[i] = max{dp[j] | wj < wi かつ hj < hi}+1 なので、w で昇順ソートしておくと、dp[i] = max{dp[j] | j < i かつ hj < hi}+1 となって、あとは hj < hi である箱 j のうちの最大の入れ子が高速にわかれば嬉しくなれる。

[1, hi) の最大値を求める部分に BIT を使うと全体で $O(NlogN)$ にできる。

w が等しい時は、h の降順でソートしておくと、更新の際に w が同じ箱同士が入れ子になるのを防げる(最大値を求める区間を考えるとわかる(語彙力がなかった。