FreeStyleWiki

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

[アルゴリズム,DP]

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

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

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

A - Frog 1

+ DPテーブル検討

  • 漸化式
    • i: 足場のインデックス, j: コストの総計 (表ではそうなっているが、iは特に必要ない)
    • dp%5Bj%5D+%3D+%5Cbegin%7Beqnarray%7D+%5Cleft%5C%7B+%5Cbegin%7Barray%7D%7Bl%7D+min%28+dp%5Bj%2D1%5D+%2B+cost%28H%5F%7Bj%2D1%7D%2C+H%5Fj%29%2C+dp%5Bj%5D+%29+%5C%5C+min%28+dp%5Bj%2D2%5D+%2B+cost%28H%5F%7Bj%2D2%7D%2C+H%5Fj%29%2C+dp%5Bj%5D+%29+%28j%3E1%29+%5Cend%7Barray%7D+%5Cright%2E+%5Cend%7Beqnarray%7D+

+ 解答(Ruby)

B - Frog 2

+ DPテーブル検討

  • 漸化式
    • i: 足場のインデックス, j: コストの総計
    • dp%5Bj%5D+%3D+%5Cbegin%7Beqnarray%7D+%5Cleft%5C%7B+%5Cbegin%7Barray%7D%7Bl%7D+min%28+cost%28H%5Fi%2C+H%5Fj%29+%2B+dp%5Bi%5D%2C+dp%5Bj%5D+%29+%5C%5C+0+%28+i%3Dj%3D1+%29+%5Cend%7Barray%7D+%5Cright%2E+%5Cend%7Beqnarray%7D+

+ 解答(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%5Bi%2B1%5D%5Bj%5D+%3D+%5Cbegin%7Beqnarray%7D+%5Cleft%5C%7B+%5Cbegin%7Barray%7D%7Bl%7D+dp%5Bi%5D%5Bj%5D+%28j+%3C+w%5Bi%5D%29+%5C%5C+max%28dp%5Bi%5D%5Bj%5D%2C+dp%5Bi%5D%5Bj%2Dw%5Bi%5D%5D%2Bv%5Bi%5D%29+%5Cend%7Barray%7D+%5Cright%2E+%5Cend%7Beqnarray%7D+

+ 解答(D言語)

E - Knapsack 2

  • Wが10^9まであるのでそのままでは解けない
  • 価値に対して重量を最小化
  • 漸化式
    • i: 品物のインデックス(縦軸), j: 品物の価値(横軸)
    • dp%5Bi%2B1%5D%5Bj%5D+%3D+%5Cbegin%7Beqnarray%7D+%5Cleft%5C%7B+%5Cbegin%7Barray%7D%7Bl%7D+min%28dp%5Bi%5D%5Bj%5D%2C+Wi+%29+%28+Vi+%3E%3D+j+%29+%5C%5C+min%28dp%5Bi%5D%5Bj%5D%2C+dp%5Bi%5D%5Bj%2DVi%5D+%2B+Wi%29+%5Cend%7Barray%7D+%5Cright%2E+%5Cend%7Beqnarray%7D+

+ 解答(Ruby)

  Typical DP Contest