динамическое программирование на подотрезках
задача: Стоимость проезда
Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе, n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте i, то он может двигаться либо до пункта i+1, либо до пункта i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (n-1) пункте, то можно просто доехать до конца шоссе, не оплачивая проезд в последнем пункте. Зная стоимость, которую необходимо заплатить в определенном пункте оплаты, помогите роботу Сильверу найти наименьшую сумму, которую он заплатит, проехав через все шоссе.
Формат входных дынных В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).
Можно подумать что стоит использовать жадный алгоритм,который на каждом шаге будет учитывать только два впереди стоящих числа и выбирать минимальное, но допустим у нас есть подотрезок: x 1 15 60 2, где x-это пунт оплаты в котором находится сильвер. Если использовать жадный алгоритм, x перейдет сначала на место единицы, а затем на место 15 и потом на 2 и итоговая сумма будет 1+15+2=18, когда можно было перейти на 15, а затем на 2 и сумма была бы 17. Каком должен быть алгоритм, чтобы решить данную задачу?
Ответы (2 шт):
Если использовать жадный алгоритм, x перейдет сначала на место единицы, а затем на место 15
Не нужно сразу выбирать финальный маршрут.
Делаете цикл от 0 до N-1. На каждой итерации определяете стоимость поездки до i-ой позиции (на основе стоимостей i-1 и i-2 позиций).
Цикл можно сделать с конца, но кажется, что разницы нет.
Если нужно восстановить маршрут, а не только финальную стоимость, то для каждой позиции хранить, из какой позиции мы в нее пришли (а потом восстаналивать маршрут с конца).
Пусть fi, 1 ≤ i ≤ n – минимальная стоимость попадания в i-тый пункт оплаты.
В условиях задачи сказано что путь пройден полностью если мы оказались в пункте n - 1 или n. Нас интересует минимум, то есть min(fn-1, fn) – ответ к задаче.
В начале f1 = c1, f2 = c2, где ci, 1 ≤ i ≤ n – стоимости оплаты в i-том пункте. Это тоже из условий.
В середине логика следущая: в пункт i можно приехать из предыдущего пункта, тогда стоимость будет fi-1 + ci. Или из предпредыдущего, тогда стоимость fi-2 + ci. Нам нужен минимум из обоих:
fi = min(fi-2, fi-1) + ci.
Эти формулы позволяют последовательно построить fi для всех i и из двух последних значений получить ответ.
Я бы ещё расширил область определения f: f-1 = f0 = 0. Если так сделать, не нужно отдельно обрабатывать первые два значения, общая формула правильно вычислит f1 и f2.
Алгоритм работает в константной памяти: чтобы вычислить следующую стоимость достаточно хранить две предыдущие и цену на следующем пункте. Что-то такое:
n = input_int()
fp = 0
f = 0
repeat n times {
c = input_int()
fn = min(fp, f) + c
fp = f
f = fn
}
print(min(fp, f))