Python

Задача на Python. Одномерное динамическое программирование

Исполнитель преобразует натуральные числа. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Прибавить 3

Первая команда увеличивает число на 1, вторая увеличивает его на 2, третья на 3. Программа для исполнителя – это последовательность команд. Исполнитель стартует с числа 1, и "шагает" до числа N. Также имеется массив price, содержащий размер платы за посещение чисел. N - длина массива price. Найти траекторию перехода от 1 к N, для которой плата будет минимальной, а также размер платы.

Входные данные - строка из элементов массива price, разделённых пробелами. Программа должна выдать в первой строке размер минимальной платы, в следующей строке оптимальную траекторию в виде списка.

Гарантируется, что траектория, позволяющая собрать минимальную плату, будет единственной.

Sample Input:

1 4 2 4 1 5 2 5 1 5 2 3 1 5 2 3
Sample Output:

13
[1, 3, 5, 7, 9, 11, 13, 16]
Напишите программу. Тестируется через stdin → stdout
Владислав Исаев
Владислав Исаев
133
Вариант с хранением одного массива под траектории (каждый элемент содержит индекс следующего элемента + 1, а при выводе выбираем только нужную траекторию):
 pen = [int(s) for s in input().split()]

minpen = (sum(pen[-2:]), pen[-1])

nexti = [-1] * (len(pen) - 1) + [len(pen)]

for i in range(len(pen) - 3, -1, -1):

    k = min(range(len(minpen)), key = minpen.__getitem__)

    minpen = (pen[i] + min(minpen),) + minpen[:2]

    nexti[i] = i + k + 2

route, i = [1], 1

while i < len(nexti):

    route.append(i := nexti[i - 1])

print(minpen[0], route, sep = '\n')
Вариант с раздельным хранением траекторий для трёх последних обработанных элементов. Хранятся только индексы траекторий, таким образом, данные для заведомо тупиковых путей не хранятся:
 pen = [int(s) for s in input().split()]

minpen = (sum(pen[-2:]), pen[-1])

nexti = ([len(pen)], [])

for i in range(len(pen) - 3, -1, -1):

    k = min(range(len(minpen)), key = minpen.__getitem__)

    minpen = (pen[i] + minpen[k],) + minpen[:2]

    nexti = ([i + k + 2] + nexti[k],) + nexti[:2]

print(minpen[0], [1] + nexti[0], sep = '\n')
Функциональная версия второго варианта:
 from functools import reduce

def call(f, *args, **kwargs): return f(*args, **kwargs)

pen, l = map(call, (reversed, len), ([int(s) for s in input().split()],) * 2)

last = next(pen)

def step(t, u):

    minpen, nexti = t; i, p = u

    k = min(range(len(minpen)), key = minpen.__getitem__)

    return ((p + minpen[k],) + minpen[:2], ([l - i + k] + nexti[k],) + nexti[:2])

(m, _, _), (ni, _, _) = reduce(

    step, enumerate(pen, 1), ((last + next(pen), last), ([l], [])))

print(m, [1] + ni, sep = '\n')
Если ещё немного помозговать, можно сделать так, чтобы для каждой из трёх последних траекторий раздельно хранилась только головная часть (индексы в пределах обрабатываемых трёх элементов), а хвост был общим. Или можно взять для этой цели дерево (собственно, списки с общим хвостом и образуют "перевёрнутое" дерево). Но по-моему, приличный язык программирования должен сам обеспечивать такие вещи. По крайней мере, LISP, Haskell и Scala обеспечивают. А Питон пока не дорос.
Жансерик Аманжолов
Жансерик Аманжолов
87 571
Лучший ответ

Похожие вопросы