質問:
ある場所から D (D <= 1,000,000,000) 単位離れた別の場所にトラックで移動したいと考えています。トラックは最大 G (G < 1,000,000) 単位の燃料を保持でき、1 単位の距離で 1 単位の燃料を消費します。途中に N (N <= 50,000) の燃料ステーションがあります。各ステーション i は開始点から X_i 単位離れており、燃料の単位あたりの価格は Y_i (Y_i <= 1,000,000) です。B単位の燃料で旅を始めます。目的地に到達するための最小コストの方法は何ですか?
( USACOの過去のコンテストからの実際の問題文)
私のアルゴリズム:
F[i] = 燃料ステーション i に到達するために必要な最小コストとし、N+1 番目の燃料ステーションを目的地とします。
k が、i に到達する前にタンクを充填する最後のステーションであるとしF[i] = F[k] + Y_k * (X_i-X_k)ます。すべての k < i に対してこれを試しX_i-X_k < D、最小のものを取ります。
F[N+1] が最終的な答えになります。
このアルゴリズムの問題:
1. O(N 2 ) 時間がかかり、2 秒の制限時間内に実行されません。
2. 燃料ステーション k にすでに m 単位の燃料があり、i に到達するために X_i-X_k-m 単位の燃料のみを充填する場合は考慮されていません。
これらの問題を解決するにはどうすればよいですか?