2002/Contest/世界大会

Problem H : A Spy in the Metro

問題概要

一本道・複線の鉄道で、できるだけ駅で立ち止まらずに、目的の駅に目的の時間にいるようにしたい。このとき、駅で立ち止まることになる最短の時間を求める。

解法

動的計画法。

time 分時点で station 駅にいれば standing time 分の待ち時間で目的地にたどり着ける、ことを表す表 :

table[time][station] = standing time

を用意し、 time = T から時間をさかのぼって表を埋めていく。 (三廻部; Mar 21, 2004)

議論

  • 純粋な思考三十分、コーディング一時間半程度だったか...?
    時間はかかったものの、動的計画を一から構築できたのには一応満足。 (三廻部; Mar 21, 2004)

ファイルを添付する

filemikurube_h.c 630件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filemikurube_h.c 630件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:50 (3153d)