Moo University(0)

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=2008
うしさんチームを作る問題。簡単じゃーん！と思って手を出したが、めっちゃくちゃ難しいことに気付いた。

A*(H-h) + B*(W-w) <= C

A,B,Cはインプットとして与えられる。
H,Wはうしさんのサイズで、これも与えられる。h,wはチーム内の最小サイズ。
で、この条件を満たすうしさんを集めてチームを作ると最大メンバー数は何人ですか？という問題。

一見、「あー、H,Wの中の最小値を求めて、条件式に当てはまるうしをカウントすればエエんやね」と思うのだが、それだとWAになる。最小サイズというのはおそらく「編成したチーム内で」ということだろうから、選ぶメンバーによって最小値はその都度変わるのだ。

「そいじゃあ再帰で可能なチーム編成の組み合わせを調べて・・・」となると、計算量がN!に跳ね上がる。H,Wのリストを別に用意して、小さい方から調べていく・・とやっても計算量はN~3くらいになってしまうだろう。

Acceptされている人の大多数はかなり短い時間で答えが出ている。ということはスゴー(ﾟдﾟ)なアルゴリズムがあるはずなのだが、私はさっぱりわからない。というわけで誰かわかる人教えて下さい。わからなくても誰か一緒に考えて〜〜〜〜！！！