fc2ブログ



上司のおごり

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 の最大値を求めます。


スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ