aoj2333:My friends are small
解法
「僕は、入れられる友達がまだ残っている限り、入れるのを止めない。決して止めない。」
という条件が厄介です。これがなければ、ただdpするだけなのですが・・・。
まず、w[0],...,w[N-1]を昇順にソートします。
w[0]を使う場合と使わない場合に場合分けしてみます。
・w[0]を使う場合：
w[1],...,w[N-1]たちについて、WをW-w[0]に更新した問題を再帰的に解けばいいです。
・w[0]を使わない場合：
w[1],...,w[N-1]たちについて、和が(W-w[0],W]に入って、極大になるようなものの通り数を求めたいです。
(和がW-w[0]以下になるものだと、w[0]を追加することができるので、極大になりません)
これは、極大という条件を考えずに、w[1],...,w[N-1]について普通のdpを行えばよいです。
普通にdpしても、(W-w[0],W]の範囲では極大になっています。(wたちをソートしているので、w[0]<=w[1],...,w[N-1]。よって、これ以上追加できず、極大。)
