BOJ-13305ガソリンスタンド解決策(C++)

問題リンク
白準13305号-ガソリンスタンド

解決策
  アルゴリズムの問題を解くには、「できるだけ複雑に考えない」ことが大切です.どんなに難しい問題(例えば、標準からダイヤモンド設計まで)でも、この考えは考えにくいかもしれませんが、多くの考えの実施過程自体は複雑ではありません(もちろん、たまにこのような場合もあります).
  本問題も同様である.問題の説明を読んですぐにわかるようになったので,本問題はGreedy Algorithmで解決できると考えた.重要なのは、あまり複雑なGreedyを考えないことです.そのためには、以下の行動が重要です.
問題のシナリオに隠されている原理や条件を見つけます.
  この問題はまさにこのような考えで解決しやすい.参考までに、実際の解決策よりも複雑なGreedyを考えた結果、最初の試みで失敗した.
  問題の状況を理解するには、次の条件を非表示にします.
「最低ガソリン代のために、ガソリンスタンドを通るたびに一番安いガソリン代を選びます.」
  つまり、ガソリンスタンドA、B、Cが一列に並んでいて、ガソリン代がA>C>Bの場合.
1)Aから出発する.最初のガソリンスタンドがAだったので、Aのガソリン代を払って、それから距離を移動します.
2)Bに達する.Bのガソリン代がAより安いなら、Bでガソリンを入れるのはもちろんいいです.
3)Cに達する.Cガソリン代Bよりガソリン代の方が安いので、無理に給油しないで進みましょう.
  そうですね.「今到着したガソリンスタンドのガソリン代より、過去に通ったガソリンスタンドのガソリン代の方が安ければ、今はガソリンスタンドでガソリンを入れる必要は全くありません.」
  この点を知れば,問題の解き方がずっと簡単になる簡単な線形軌跡で解決できます.具体的な実施については、多くの説明は必要ありません.次はコードです.

#include <iostream>
#include <climits>
// BOJ - 13305 Gas Station
using namespace std;

int cost[100001], dist[100001];

long long solve(int n) {
	int MINcost = INT_MAX;
	long long dist_sum = 0;
	
	for (int i = 1; i < n; i++) {
		if (cost[i] < MINcost) MINcost = cost[i];
		dist_sum += (long long)MINcost * (long long)dist[i];
	}

	return dist_sum;
}

int main(void) {
	int n;
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n;
	for (int i = 1; i < n; i++) cin >> dist[i];
	for (int i = 1; i <= n; i++) cin >> cost[i];
	cout << solve(n);

	return 0;
}

  Greedyを設計する際,どのような隠れた条件が問題を非常に簡単に変えることができるかを見つけることに慣れている.