Здесь мы разберем решение задачи "Головоломка умножения".
В головоломку умножения играют с рядом карт, каждая из которых содержит
одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает
число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно
слева и справа от нее. Не разрешено убирать первую и последнюю карты ряда. После последнего хода
в ряду остается только две карты.
Цель игры - убрать карты в таком порядке, чтобы минимизировать общее количество
набранных очков.
Ограничения: 3 ≤ N
≤ 50, числа на картах целые от 1
до 50, время 1с. [1].
В этой задачи нужно найти только минимальное количество очков, то есть оптимальный параметр для всей задачи. Значит, четвертый этап построение алгоритма задачи, решаемой методом динамического программирования, не понадобиться (шаг 2). Эту задачу можно разбить на несколько подзадач. В начале убираем карту k, при этом подсчитываем количество очков и заносим эти очки в специальную таблицу B. Очки считаются по следующей формуле b[i, j] = b[i, k] + b[k, j] + vivkvj, где vi - это числа на картах. То есть далее нужно работать уже с последовательностями карт vi..k и vk..j. В каждой из этих последовательностей также убираем некоторую карту. Это действие будет продолжаться до тех пор, пока карт в последовательностях не станет равно двум. При этом при подсчете учитываем, что количество очков должно быть минимальным. Следовательно, нужно организовать двумерный массив, где будут храниться эти минимальные значения, то есть массив B. Также следует предусмотреть то, что одни и те же значения будут вычисляться по несколько раз, то есть это надо исключить из программы. Для поиска минимального количества очков написана рекурсивная функция. Эта функция, заполняя матрицу B, находит минимальное количество очков. В начале эта она вычисляет минимальное значение, если первым убрать второй элемент последовательности, затем, если первым убрать третий, и так далее. И при этом, ищется минимальное значение из всех возможных ситуаций.
Текст этой функии и само решение задачи вы можете посмотреть
здесь.
(1)Меньшиков Ф.В. Олимпиадные задачи по программированию. - СПб: Питер, 2006. - 315с.
На следующем шаге мы разберем решение задачи о НОП.
