8VC Venture Cup 2016 - Final Round (Div. 1) D. Package Delivery

codeforces.com

問題概要

n リットルのガソリンを蓄えられる車を使って x=0 から x=d に移動したい。 単位距離移動するごとにガソリンを 1L 消費する。初期状態ではタンクは満タンである。

数直線上に m 個のガソリンスタンドがあり、位置 x[i] にあるガソリンスタンドのガソリンの価格は 1L あたり p[i] 円である。各ガソリンスタンドではタンクの容量を超えなければ好きな量のガソリンを補充できる。

移動するのに必要なコストの最小値を求めよ。

解法

x[i] より後ろにあり、p[i] より安くて最も x[i] に近いガソリンスタンドを next[i] とする。

現在ガソリンスタンド i にいるとしたとき次のような行動をとるのが最適。

(1) x[next[i]]-x[i] がタンク容量を超える場合
現在いるガソリンスタンドで満タンにして、i+1 に移動する。

(2) x[next[i]]-x[i] がタンク容量以下の場合
next[i] に到達するのに最低限必要な量まで補給し、next[i] に移動する。

Submission #16422027 - Codeforces

8VC Venture Cup 2016 - Final Round (Div. 1) D. Pac ...

本番中思いつけず。貪欲は難しい。