上司のおごり
2009.09.07 22:43 パソコン甲子園 2009
パソコン甲子園2009予選 問題08 上司のおごり
典型的な動的計画法の問題です。
K[i] を i 番目の金額、
Ti[j] を i 番目までの金額を使って j を払えるかのフラグとする (1の場合に払えるものとする)と、
T0[j] を 0 で初期化し、
Ti[j] = Ti-1[j] | Ti-1[j - K[i]]
となります。
あとは、i が素数で T[i] が 1 である i の最大値を求めます。
問題はこちら。
典型的な動的計画法の問題です。
K[i] を i 番目の金額、
Ti[j] を i 番目までの金額を使って j を払えるかのフラグとする (1の場合に払えるものとする)と、
T0[j] を 0 で初期化し、
Ti[j] = Ti-1[j] | Ti-1[j - K[i]]
となります。
あとは、i が素数で T[i] が 1 である i の最大値を求めます。
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |