13305号:ガソリンスタンド

質問する

13305号：ガソリンスタンド

に近づく

N都市、N-1本の幹線と街、N個のガソリンスタンドのガソリン価格

が初めて移動する場合は、給油して(첫 주유소 가격 * 첫 이동 거리)台移動する必要があります.

最後の都市

にあるガソリンスタンドのガソリン価格は実際には意味がありません(到着後ガソリンを入れる必要がないため)

上記の条件を考慮して,貪欲な方法で解くとよい.

マイコード

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] dist = new long[n-1];
        long[] cost = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n-1; i++) {
            dist[i] = Long.parseLong(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            cost[i] = Long.parseLong(st.nextToken());
        }
        long sum = 0;
        long tmp = cost[0];
        for (int i = 0; i < n-1; i++) {
            if (tmp > cost[i]) tmp = cost[i];
            sum += (tmp * dist[i]);
        }

        System.out.println(sum);
    }
}

入力条件の範囲を考慮して、タイプをintではなくlongに設定します.
(問題を正しく読んでスキップしなければなりません...)