日記

のみろぐ

主に競プロ日記です

AOJ

コイン問題

考察 状態変数を考える dp[i円の最小枚数]でいけそう。50000円がMaxだから制約的にも行けそう 次に遷移を考える dp[i] ← dp[i-c[j]] + 1みたいな感じで行けそう。計算量も$O(nm)$で余裕がある。最大で$106$ステップだし 解法 dp[i円の最小枚数]という状態を…

観音堂

考察 状態変数を考える dp[i段目までの組み合わせの個数]で出来そう 次に状態遷移を考える 初期位置から1, 2, 3段目は1通りあるので、dp[1] = dp[2] = dp[3] = 1で初期化する。 遷移はdp[i+1] += dp[i]とかで出来そう 解法 dp[i段目までの組み合わせの個数]…

DPL_1_C「ナップザック問題」

DPL_1_C「ナップザック問題」 考察 DPに使いそうな値を考える 今回は01ナップザックみたいに何個目まで選んだかという情報は必要無い 価値と重さが分ればいいかなーってなる 価値と重さだけわかれば良いので1次元のDPでできそう 同じ種類の荷物は何個でも使…

DPL_1_B「0-1 ナップザック問題」

DPL_1_B「0-1 ナップザック問題」 DPL_1_B「0-1 ナップザック問題」 解法 漸化式 部分的に見る コード 要点 解法 上図のようなDPテーブルを用意する テーブルをすべて$0$で初期化する(グローバルに宣言していれば初期化する必要は無い) 漸化式を立て、それを…

DPL_1_A「コイン問題」

DPL_1_A「コイン問題」 DPL_1_A「コイン問題」 考察 解法 漸化式 おまけ コード 要点 類題 感想 考察 価値の高いコインから順番に使う貪欲法で解けるのでは? でも、ちょうど$n$円払いたいので、貪欲ではうまくいかない時がある。 例えば、$n=10, m=4, c = {…