10776. Путешествие на машине

Имеются n городов. Вы хотите поехать из города 1 в город n на машине. Для этого нужно купить бензин. Как известно, один литр бензина в k - ом городе стоит cost_k. Изначально Ваш топливный бак пуст, и Вы расходуете один литр бензина на километр. Города расположены на одной линии в порядке возрастания, причем k - ый город имеет координату x_k. Также необходимо заплатить toll_k, чтобы въехать в k - ый город. Ваша задача – совершить поездку с минимально возможной стоимостью.

Вход. Первая строка содержит количество городов n (1 ≤ n ≤ 1000).

Вторая строка содержит n координат городов x₁, ..., x_n. Координаты уникальны и отсортированы, x_i < x_i+1 для каждого i = 1, 2, ..., n – 1.

Третья строка содержит n целых чисел – стоимости бензина cost₁, ..., cost_n.

Четвертая строка содержит n целых чисел – въездные пошлины toll₁, ..., toll_n.

Известно, что координаты городов, стоимость бензина и въездные пошлины – неотрицательные целые числа, не превышающие 10⁹.

Выход. Выведите минимально возможную стоимость поездки.

Пример входа	Пример выхода
5 1 4 5 8 10 6 8 2 4 6 7 2 5 4 7	53

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пронумеруем города от 0 до n – 1. Пусть dp_i содержит минимальную стоимость поездки до города i. Тогда dp₀ = toll₀ (для попадания в нулевой город достаточно заплатить только въездную пошлину).

Предположим, что для приезда в i-ый город мы заправились в j-ом городе и поехали в i-ый напрямую. Тогда для совершения этого переезда на бензин следует потратить cost_j * (x_j – x_i) денег. Для въезда в i-ый город следует заплатить пошлину toll_i. Стоимость проезда с первого до j-го города равна dp_j. Город j следует выбрать таким образом, чтобы минимизировать стоимость поездки. Отсюда имеем:

Пример

Рассмотрим приведенный пример.

dp₀ = toll₀ = 7,

dp₁ = toll₁ + cost₀ * (x₁ – x₀) + dp₀ = 2 + 6 * (4 – 1) + 7 = 27,

dp₂ = toll₂ + min(cost₀ * (x₂ – x₀) + dp₀, cost₁ * (x₂ – x₁) + dp₁) =

5 + min(6 * (5 – 1) + 7, 8 * (5 – 4) + 27) = 5 + min(31, 35) = 36

dp₃ = toll₃ + min( cost₀ * (x₃ – x₀) + dp₀,

cost₁ * (x₃ – x₁) + dp₁,

cost₂ * (x₃ – x₂) + dp₂) =

4 + min(6 * (8 – 1) + 7, 8 * (8 – 4) + 27, 2 * (8 – 5) + 36) =

4 + min (49, 59, 42) = 46

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);

x.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &x[i]);

cost.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &cost[i]);

toll.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &toll[i]);

Инициализируем массив dp.

dp.resize(n);

dp[0] = toll[0];

Последовательно вычисляем значения dp₁, dp₂, …, dp_n-1.

for (i = 1; i < n; i++)

{

В переменной cst вычисляем

long long cst = INF;

for (j = 0; j < i; j++)

cst = min(cst, cost[j] * (x[i] - x[j]) + dp[j]);

dp[i] = toll[i] + cst;

}

Выводим ответ.

printf("%lld\n", dp[n - 1]);