漸化式を立てる練習(2)
- 漸化式を立てるトレーニング
- モチベーションもあるので楽なやつからやる
Educational DP Contest / DP まとめコンテスト
- ある程度速い言語の使用を推奨します (例: C++, Java)。 、Ruby「ほな…また…」
- 解説
- A,B,C,D,Eまで 動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集
- F,G,H,I,Jまで Educational DP Contest の F ~ J 問題の解説と類題集
A - Frog 1
+ | DPテーブル検討 |
- 漸化式
- i: 足場のインデックス, j: コストの総計 (表ではそうなっているが、iは特に必要ない)
-
+ | 解答(Ruby) |
B - Frog 2
+ | DPテーブル検討 |
- 漸化式
- i: 足場のインデックス, j: コストの総計
-
+ | 解答(Ruby with TLE) |
+ | 解答(D言語) |
C - Vacation
+ | DPテーブル検討 |
- 漸化式
- i: 活動のインデックス(日), j: 各活動のインデックス, 各セル: iの日にjのインデックスを行った場合の幸福度の総和の最大値
-
+ | 解答(Ruby) |
D - Knapsack 1
- これは 漸化式を立てる練習(1) でやったやつと同じやろ
- 01ナップサック問題 と同じ
- 重さに対して価値を最大化
- 漸化式
- i: 品物のインデックス(縦軸), j: ナップサックの容量(横軸)
-
+ | 解答(D言語) |
E - Knapsack 2
- Wが10^9まであるのでそのままでは解けない
- 価値に対して重量を最小化
- 漸化式
- i: 品物のインデックス(縦軸), j: 品物の価値(横軸)
-
+ | 解答(Ruby) |