AOJ2333 僕の友達は小さい
AOJ-ICPC 500 自力AC！！！！
My friends are small | Aizu Online Judge
問題概要
人の友達がいて、
番目の友達の重さは
である。
この友達を好きな順で選択し、選択した友達の重さの総和が を超えないようにしたとき、選択した友達の組み合わせは何通りあるか。ただし、選択できる友達が残っている場合はその友達は選択しなければならない。
制約
解法
「選択できる友達が残っている場合はその友達は選択しなければならない」の制約がない場合は普通のナップサック問題となり、
dp[i][j] := iまで見て重さの総和がjのときの場合の数
とすればよい。
「選択できる友達が残っている場合はその友達は選択しなければならない」を言い換えると、「選択した友達の重さの総和 + 選択してない友達の最小の重さ を満たさなければならない」となる。
よって、選択していない友達のうち、重さが最小の情報を保持してあげればよい。
dp[i][j][k] := iまで見て重さの総和がjで、選択していない重さ最小の友達のindexがkのときの場合の数
とすると、DP後で を満たす dp[n][j][k]のみを答えに加算してあげればよい。
計算量は となって間に合うが、dp[200][10000][200]では配列が足りなくなるので、1次元目を使いまわしてdp[2][10000][200]とすればよい。
