問題 - Railway tickets -

問題 - Railway tickets • 数直線上のN個の駅(2以上10000以下)
• 距離に応じたチケット料金
– 距離L1 までは値段 C1
– 距離L2 までは値段 C2
– 距離L3 までは値段 C3
• ２駅間の最安チケット料金を求める
細かい条件
• L や C は int に収まる
– 1<=L1<L2<L3<=10^9, 1<=C1<C2<C3<=10^9
– int の最大値は 2G～2*10^9+α
• 全ての駅は連結している
– 駅間はL3を超えないので道はある
• 最初の駅は座標 0
• 残りの駅は絶対座標が与えられる
方針
• 力ずくの探索→１００００駅あるので無理
• 主なやり方は２通り
– グラフと見立ててダイクストラ
– ＤＰ（動的計画法）
• ここでは最も簡便と思われるＤＰを説明
– 実際にスタッフが作成したソースを元に説明
入力データ構造
• 問題文通りに素直に入力
int L[3], C[3];
int numStation;
int indexStartStation;
int indexEndStation;
vector<int> positionOfStations;
入力データのパーズ
• 駅の番号は内部0-origin,外部1-origin とする
{
}
// load data
cin >> L[0] >> L[1] >> L[2];
cin >> C[0] >> C[1] >> C[2];
cin >> numStation;
positionOfStations.resize(numStation);
cin >> indexStartStation; indexStartStation--;
cin >> indexEndStation;
indexEndStation--;
positionOfStations[0] = 0;
for(int i = 1; i < positionOfStations.size(); i++) {
cin >> positionOfStations[i];
} // fori
左右の入れ替え
• 始駅の駅番号sと終駅の駅番号dがs<dとな
るように変換
if(indexStartStation > indexEndStation)
swap(indexEndStation, indexStartStation);
Dynamic Programming
始駅
終駅
駅番号
2
3
4
5
6
位置
コスト
20
0
34
15
48
38
89
122
距離L1まで
３８＋C1
距離L２まで
15＋C2
距離L３まで
0＋C3
最も安い
コストを
選択する
ＤＰの初期化
• 最小コストは10^9を超えないので10^9+1で
初期化
vector<int> minimalCost(numStation, 1000000001);
minimalCost[indexStartStation] = 0;
DPループ
• ある駅を固定し、前の駅を距離L3まで考慮
for(int idx = indexStartStation + 1; idx <= indexEndStation; idx++) {
int lengthType = 0;
int indexOfPrevStation = idx - 1;
while(indexOfPrevStation >= 0 && lengthType < 3) {
while(lengthType < 3 && abs(positionOfStations[idx] –
positionOfStations[indexOfPrevStation]) > L[lengthType]) {
lengthType++;
}
if(lengthType < 3) {
minimalCost[idx] = min<int>(minimalCost[idx],
minimalCost[indexOfPrevStation] + C[lengthType]);
}
indexOfPrevStation--;
}
}
結果の表示
cout << minimalCost[indexEndStation] << endl ;

Download Report