動的計画法に関するカテゴリーです。

AtCoder, 動的計画法

問題方針

動的計画法を行います。\( N \) 回のジャンケンにおいてジャンケンの手が制約されるグループは \( K \) 個存在します。例えば、\( K = 2 \) のとき、\( 0, 2 ,4, \cdots \) と \( 1, ...

AOJ, 動的計画法, 文字列

問題方針

動的計画法を行います。\( d(i, j) \) を \( t \) の \( j \) 番目までの部分文字列において、\( b \) の \( j \) 番目までの部分文字列の出現回数とします。初期値は、\( d(i, 0) ...

AOJ, 動的計画法

問題方針

\( d(i) \) を文字 \( i \) の出口への行き方の数として、動的計画法を行います。初期値は \( d(s_0) = 1\) とします。更新式は、\( d(s_i) \leftarrow d(s_i) + d(t_ ...

AOJ, bitDP, 動的計画法

問題方針

\( i \) 列目に荷物が置けるかどうかは \( i – 1 \) 列目と \( i \) 列目を調べれば良いので、動的計画法を行います。各列の状態は荷物か置けるマスがあるかどうかの \( 2 \) 通りであり ...

yukicoder, 動的計画法

問題方針大きさが異なっている隣り合う餅をずんだ餅にする場合

この場合、大きさが小さい餅が消えてしまうので適切ではありません。例えば、\( A = (1, 2, 3, 4, 5) \) の配列において、\( 1 \) 番目と \( 2 \ ...

AtCoder, 動的計画法

問題方針

動的計画法を行い、\( X \) を作れるかどうかを調べます。\( i \) 円が作れるとき、\( i + 100 \) 円も作れるというような方針で実装します。

コード

 

AOJ, 動的計画法

問題方針

\( 3 \) 日以上同じパスタを選んではいけないという制約がポイントです。\( i + 1 \) 日目の予定を決めるためには、\( i \) 日目と \( i – 1 \) 日目の予定が影響することを考えて動的計 ...

AOJ, 動的計画法

問題方針

\( i \) 日目に着ることができる服の派手さの最小値を \( v_i \), 最大値を \( w_i \) とします。各日において派手さの最小値または最大値を持つ服を選ぶことが最適なので、次の動的計画法を行います。証明はし ...

AOJ, 動的計画法

問題方針

前日と今日のスケジュールの状態を考えれば良いので、動的計画法を行います。便宜上、与えられた文字列の先頭に ‘J’ を挿入します。ここで、\( d(i, j) \) を \( i \) 日目の参加者の状態 ...

AOJ, 動的計画法

問題方針最小値を固定

水ようかんを切り分けた時の長さの値は、切る箇所を任意の \( 2 \) 点選ぶことを考えると、最大でも

\

あることが分かります。したがって、最小値を固定したときの、最大値を変数とみて、最大 ...