Условие задачи Колода карт состоит из N (1≤N≤200) карт, пронумерованных от 1 до N. На столе имеется N ячеек, расположенных в один ряд. Все ячейки пронумерованы от 1 до N. Каждая ячейка в начале игры содержит ровно одну карту. Необходимо сложить все карты в колоду на произвольной ячейке таким образом, чтобы внизу лежала карта N, на ней – карта с номером N-1, а на самом верху колоды – карта с номером 1. Таким образом, вся колода карт окажется сложенной в одной ячейке, а остальные ячейки будут пустыми.
При раскладывании пасьянса разрешается только одна операция: можно перенести карту с номером M и лежащие на ней карты (если таковые имеются) на карту с номером M+1. За каждую такую операцию переноса игроку начисляется штраф, равный расстоянию, на которое переносится стопка карт, т.е. разности в номерах мест ячеек.
Напишите программу, определяющую минимальный штраф, который может быть получен при складывании пасьянса из заданной конфигурации.
Ввод: Вначале задаётся N – число карт пасьянса. Затем следует N чисел – номера карт, выложенных в ячейках, в начале игры. Карты задаются в порядке нарастания номеров ячеек, в которые они выложены.
Вывод: Напечатать минимальную величину штрафа. Структура решения – порядок перекладываний в произвольном формате.
В данной работе вам предстоит решить задачу дискретной оптимизации несколькими способами: рекурсивно; рекурсивно с мемоизацией (запоминанием);
Результатом работы должен стать отчет в текстовом формате, который должен содержать:
Математическую модель задачи с пояснением ко всем введенным вами обозначениям и полученным рекуррентным соотношениям;
Предварительные теоретические оценки сложности (и по времени, и по требуемой памяти) для рекуррентной версии решения и решения методом динамического программирования;
Код каждого из вариантов решения;
Выводы по проделанной вами работе.
В рекуррентных версиях достаточно значения оптимизируемого параметра.
Программа пишется в Code::Blocks на c++