mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ AOJ 問題 My friends are small | Aizu Online Judge 解法 ある集合が有効かどうかを調べるときは, 「まだ選ばれていないやつの中で一番重さの小さい友達をリュックの中に入れることができないか」というのが判定基準になります。そこで, 配列 w をソートしたのち, 「[0, i) はすべて選ぶけど i 番目は選ばないような場合の数」というのを考えます。sum = w[0]+...+w[i-1] とすると, 残りの入れる量は W-sum です。dp[k] = ([i+1, N) の区間の友達を使って, 合計重さを k にする場合の数) の dp をしたとき, W - … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F07%2F15%2F105102" title="AOJ 2333 My friends are small - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-07-15 10:51:02 rich https://mayokoex.hatenablog.com/entry/2016/07/15/105102 1.0 100%