回答編集履歴
1
コメントに対する追記
answer
CHANGED
|
@@ -9,4 +9,16 @@
|
|
|
9
9
|
|
|
10
10
|
このまま愚直に実装するとメモリを大量に使う上、無駄な計算に時間がとられますが、DP配列を使いまわすようにしたり、DPの長さをPまで切り詰める（Pに到達可能なガソリンがある状態から補給する必要がない。超えた部分は別途管理する）ようなことをすれば数分~数十分レベルまで実行時間を短くできるでしょう。
|
|
11
11
|
|
|
12
|
-
ちなみにこの問題は部分和問題の一種のようなので、おそらくこれ以上に効率のいいアルゴリズムはないんじゃないかと思います。本当にこの問題設定であってますか?
|
|
12
|
+
ちなみにこの問題は部分和問題の一種のようなので、おそらくこれ以上に効率のいいアルゴリズムはないんじゃないかと思います。本当にこの問題設定であってますか?
|
|
13
|
+
|
|
14
|
+
---
|
|
15
|
+
当初の問題設定だと、ガソリンを補給する量が多すぎても少なすぎてもダメなので、ガソリンをどれだけ補給したか正確に記録しておく必要があります。
|
|
16
|
+
> DP[i][g + Gi] = DP[i - 1][g] or DP[i - 1][g + Gi]（ただし g >= Pi )
|
|
17
|
+
この部分についてですが、
|
|
18
|
+
「i番目のガソリンスタンドにたどり着くには、i-1番目までのガソリンスタンドでもっている保有量と等しいかそれ以上(但し保有量の方がガソリンスタンドで補給する量と等しいかそれ以上)」
|
|
19
|
+
という意味でしょうか。
|
|
20
|
+
|
|
21
|
+
なのでDP[i][g + Gi]はぴったりg + Giのガソリンを補給することが可能かどうかを表しています。
|
|
22
|
+
右辺を分解すると、DP[i - 1][g + Gi]がi番目のガソリンスタンドを使わない場合で、DP[i - 1][g]がi番目のガソリンスタンドを使わない場合です。（この点最初の式は不正確で、実際にはg + Gi >= Pi and g < Pi の時にはDP[i][g] = DP[i - 1][g]が成り立ちます)
|
|
23
|
+
|
|
24
|
+
とはいえ最小回数を求めるだけならこの辺は全く関係なく、プライオリティキューをつかって貪欲に補給していくだけで計算可能です。詳しくはPOJ 2431という条件が違うだけの問題が有名なので、その解説を参考にしてください。
|