動的計画法を用いてこの問題を解きます。

まず、部屋をランクの昇順に割り当てましょう。このとき、部屋 \(i\) には希望が \(R_i\) 以下の人が入ることが出来ると言い換えると、以下のような動的計画法が設計できます。

dp[\(i\) 番目の部屋まで入る人を決めた] [ \(j=\) \(i\) 番目までの部屋に割り当てられていない人の数] = 必要なコストの最小値

この dp は、\(i\) 番目の部屋にお金を支払う場合、入れられる最大人数を入れて良いことを考慮すれば、状態数 \(O(N^2)\) 遷移 \(O(1)\) で動作するため、\(O(N^2)\) でこの問題を解くことができます。