ABC038 D プレゼント
問題概要
個の箱が与えられる。 番目の箱は縦 cm × 横 cmで、縦と横を入れ替えることはできない。
ある箱は縦・横ともにより大きいサイズの箱にのみ入れることができ、ある箱は1つまでしか他の箱を入れることはできない。
このとき、箱を最大で何重の入れ子にできるかを求めよ。
制約
部分点は
部分点解法
dp[i][j] := 縦icm × 横jcm の箱に入る箱の数
としてdpをする。
と は大きいのでそのままではdp配列の添字にはできない。よって、 を利用して座圧を行う。
満点解法
「ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができる」という性質から、入れ子にする箱を小さい順にならべると、 と がともに単調増加になっていることがわかる。つまり、縦の長さで昇順になるように並び替えた後、横の長さでも昇順になるように順番に箱を選んでいけばいいことがわかる。
ただし、縦の長さが等しい2つの箱があった場合、どちらか片方の箱しか選択できないことに注意しなければいけない。
普通の昇順ソートを行うと、キーを2つもつ場合は、 かつ のとき が先に来るように並び替えられてしまうが、これだと縦の長さでソートしたあとに横の長さだけに着目して箱を選ぶと、縦の長さが等しい箱を2つ以上選んでしまう危険性がある。
よって、 かつ のとき が先に来るように並び替えるようにする。
このように縦の長さでソートした後は、横の長さのみに着目しても「ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができる」を達成することができる。
あとは横の長さを数列の要素とした最大増加部分列(LIS)を求めてあげると、それが答えとなる。
感想
この問題を機にLISを真面目に勉強してスライドをつくったので下手ですが見てください
LIS.pdf - Google ドライブ