FreeStyleWiki

漸化式を立てる練習(2)

このエントリーをはてなブックマークに追加

[アルゴリズム,DP]

漸化式を立てる練習(2)

  • 漸化式を立てるトレーニング
  • モチベーションもあるので楽なやつからやる

  Educational DP Contest / DP まとめコンテスト

A - Frog 1

+ DPテーブル検討

  • 漸化式
    • i: 足場のインデックス, j: コストの総計 (表ではそうなっているが、iは特に必要ない)
    • dp[j] = \begin{eqnarray} \left\{ \begin{array}{l} min( dp[j-1] + cost(H_{j-1}, H_j), dp[j] ) \\ min( dp[j-2] + cost(H_{j-2}, H_j), dp[j] ) (j>1) \end{array} \right. \end{eqnarray}

+ 解答(Ruby)

B - Frog 2

+ DPテーブル検討

  • 漸化式
    • i: 足場のインデックス, j: コストの総計
    • dp[j] = \begin{eqnarray} \left\{ \begin{array}{l} min( cost(H_i, H_j) + dp[i], dp[j] ) \\ 0 ( i=j=1 ) \end{array} \right. \end{eqnarray}

+ 解答(Ruby with TLE)

+ 解答(D言語)

C - Vacation

+ DPテーブル検討

  • 漸化式
    • i: 活動のインデックス(日), j: 各活動のインデックス, 各セル: iの日にjのインデックスを行った場合の幸福度の総和の最大値
    • dp[i][j] = \begin{eqnarray} \left\{ \begin{array}{ll} max( dp[i-1][1] + A_i, dp[i-1][2] + A_i )  ( j == 0 ) \\ max( dp[i-1][0] + B_i, dp[i-1][2] + B_i )  ( j == 1 ) \\ max( dp[i-1][0] + C_i, dp[i-1][1] + C_i )  ( j == 2 ) \end{array} \right. \end{eqnarray}

+ 解答(Ruby)

D - Knapsack 1

  • 漸化式
    • i: 品物のインデックス(縦軸), j: ナップサックの容量(横軸)
    • dp[i+1][j] = \begin{eqnarray} \left\{ \begin{array}{l} dp[i][j] (j < w[i]) \\ max(dp[i][j], dp[i][j-w[i]]+v[i]) \end{array} \right. \end{eqnarray}

+ 解答(D言語)

E - Knapsack 2

  • Wが10^9まであるのでそのままでは解けない
  • 価値に対して重量を最小化
  • 漸化式
    • i: 品物のインデックス(縦軸), j: 品物の価値(横軸)
    • dp[i+1][j] = \begin{eqnarray} \left\{ \begin{array}{l} min(dp[i][j], Wi ) ( Vi >= j ) \\ min(dp[i][j], dp[i][j-Vi] + Wi) \end{array} \right. \end{eqnarray}

+ 解答(Ruby)

  Typical DP Contest