AOJ 2333 : 僕の友達は小さい

DPだろうなということは目星がつく。
ただ

僕は、入れられる友達がまだ残っている限り、入れるのを止めない。決して止めない。

この条件を満たすようにするにはどうするか
を考える必要がある。

ここで、リュックに詰めなかった一番小さい友達を状態に持って置けば
最後に組み合わせを足すところで判定できそうということが分かる。
これを「wを昇順にソート」しておくことで、
「一番最初にskipしたのはいつか」に状態が変わり、扱うのが楽になる
（しなくても解けることには解ける）。

あとはDPを書けば良い。
O(n^2 W)だが、Time Limt:8 secなのでまず大丈夫だろう（最大ケースで2, 3秒くらい？）。

最初DPテーブルを
dp[何番目までの友達まで考慮したか(n + 1)][最初にskipしたのはいつか(n + 1)][容量(W + 1)]
としていてRE（メモリエラー）をもらってしまった。
一番最初の次元は今と次しか考慮しなくていいので、
削ることができる。

ただ書くのが面倒なので、メモリが危ないときだけにしたい。
普段からこちらを書いておく練習も必要そうだが…。

それにしても、始めたばかりの頃はDPは分からなかったし、
「1,000,000,007 で割った余りを出力せよ」なんて言われたら
まず解けないと思っていたのが思い出される。
進歩は遅いけど、成長はしているんだなあ。
少しうれしい。