Динамическое программирование; разбор задач Открытой олимпиады

Начинаем разбор задач VII Открытой олимпиады школьников по программированию, 2012/13 учебный год

• Условия применения методов динамического программирования
• Разбор простой задачи («платная лестница»)

• Разбор уже решённых задач: «последняя цифа числа Фибоначчи», «Покупка билетов»

• Разбор задачи 1-B oolym-2013-1-bN.py

Домашнее задание

1. Прочитать про динамической подход на сайте MCCME (ссылки «Теоретический материал» на странице задач по динамическому прогнраммированию)

2. Запрограммировать генератор входных данных и решение задачи «платная лестница»:
   • Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.

   • 2013-03-22.paystep.py

3. В решении задачи 1-B присутствует ошибка: рассматриваются варианты, в которых число перед v_i может состоять из одних только нулей. Исправить её.

   • oolym-2013-1-bN.py

4. «Маршрут черепашки» (MCCME). В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы. Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.

   • Формат входных данных. В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

     Формат выходных данных. Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

   • 2013-03-22.turtle.py

5. Решить задачу «Распил брусьев». Вам нужно распилить деревянный брус на несколько кусков в заданных местах. Распилочная компания берет k рублей за распил одного бруска длиной k метров на две части в любом месте. Определите минимальную стоимость распила бруса на заданные части.

   • Формат входных данных. Первая строка входных данных содержит целое число L (2≤L≤106) - длину бруса и целое число N (1≤N≤100) - количество распилов. Во второй строке записано N целых чисел С_i (0<C_i<L) в строго возрастающем порядке - места, в которых нужно сделать распилы.

     Формат выходных данных. Выведите одно натуральное число - минимальную стоимость распила.

   • 2013-03-22.raspil.py

6. Попробовать порешать задачи первого тура Открытой олимпиады

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh