ねこ鍋改造計画（仮） (AOJ 2237)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2337

問題

略

解法

DP+尺取メソッドで解く。まずオス、メスを考慮せずにcuteが低い順にソートする。次にcuteの上界 $C_{\rm max}$ と下界 $C_{\rm min}$ を固定してDPを計算する。DPは2*Wの大きさで、各性別について重さwのねこ鍋を作れるかどうかと作れる場合は作るのに必要な最小のcuteのねこのindexを入れておく。ここでcuteの範囲は固定されているし、ある重みが作れるかどうかは既に計算したのでO(W)で ${\rm min}(M_{\rm max}-M_{\rm min})$ が計算できる。ここで $C_{\rm max} - C_{\rm min}$ の方が大きい場合はcuteの下界を上げる。 $M_{\rm max} - M_{\rm min}$ の方が大きい場合はcuteの上界を上げる。cuteの上界、下界を上げた際のDPの更新はO(W)でできるので、全体でO(NW)で計算可能。