Задача 98777

Тема:    [ Динамическое программирование (прочее) ]

Сложность: 2 Классы: Название задачи: Дорога.

Условие

Даны натуральные числа n > 2 и m и вещественный массив А [1:m, 1:m, 1:n - 1].Найти минимальное значение суммы.

R = A [i₁, i₂, 1] + A [i₂, i₃, 2] + A [i_n-1, i_n, n-1]

Для возможных наборов целых чисел 1< i₁, i₂, ... , i_{n < m.}

Пояснение. Числа m, n - величины порядка нескольких десятков. Поэтому неприемлемо решение с числом действий порядка mⁿ.

Источники и прецеденты использования

олимпиада
Название	Московская городская олимпиада по информатике
год
Год	1984
задача
Номер	2