読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

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]。よって、これ以上追加できず、極大。)

考察通りに再帰でやってもいいですが、再帰を展開するような感じのことができるので、forループで書けます。

コード