![想定解法
? 動的計画法
? 次の日に泊まるホテルを決めて遷移
? 宿泊費合計にそのホテルの宿泊費を加算
? 前日のホテルと違うホテルに泊まるなら、移動回数増加
? あとは、DP表を利用して辞書順最小を求める
[0] [1] [2] [3]
[0] (0, 0) - - -
[1] - (5500, 0) (5480, 0) (5500, 0)
[2] - (10980, 1) (11260, 0) (10980, 1)
[3] - (16480, 1) (16960, 2) (16480, 1)
[4] - (21980, 1) (22460, 2) (21980, 1)
前日宿泊したホテル
何泊目
(最小宿泊費, 最小移動回数)
のペア](https://image.slidesharecdn.com/cpublic-130903082242-/85/Problem-C-4-320.jpg)
Problem C
- 1. Problem C Hotel ホテル探し Aizu Camp 2013 Day1 9/3 @Respect2D
- 2. 問題概要 ? N個のホテルがある ? それぞれD泊分の宿泊費が入力される ? 最小金額でD泊泊まれるホテルのプランを出力 ? 1通りでないならD泊分のホテル移動回数を最小化 ? それでも1通りでないなら、辞書順最小で ? サンプル 3 4 ←NとD 5500 5500 5500 5500 5480 5780 5980 5980 5500 5500 5500 5500 ? D泊の最小金額は21980円 ? その中でもホテル移動回数の最小は2 ? プランA = {2, 1, 1, 1} ? プランB = {2, 3, 3, 3} ? 辞書順最小なのはプランA
- 3. 誤解法 ? 各宿泊で一番安いホテルを貪欲に選ぶ ? ダメ ? 最小の宿泊費は満たせるけど ? ホテルの最小移動回数が満たせない ? DPしましょう
- 4. 想定解法 ? 動的計画法 ? 次の日に泊まるホテルを決めて遷移 ? 宿泊費合計にそのホテルの宿泊費を加算 ? 前日のホテルと違うホテルに泊まるなら、移動回数増加 ? あとは、DP表を利用して辞書順最小を求める [0] [1] [2] [3] [0] (0, 0) - - - [1] - (5500, 0) (5480, 0) (5500, 0) [2] - (10980, 1) (11260, 0) (10980, 1) [3] - (16480, 1) (16960, 2) (16480, 1) [4] - (21980, 1) (22460, 2) (21980, 1) 前日宿泊したホテル 何泊目 (最小宿泊費, 最小移動回数) のペア
- 5. 辞書順生成について ? 前ページのように1泊目から順番にDP をすると辞書順で逆辿りが不可 ? 単純に辞書順で逆辿りしたいなら、 D泊目から順番にDPをするとよい ? その他 ? 1泊目からDPしながら、辞書順の解を生成 していくのもOKです ? メモ化再帰でもOKです
- 6. 結果 ? First AC ? rankalee ? Accept / Submit ? 15 / 67 (22.39 %)